HDU-2546 饭卡 题解 | ACM

首先这是一道典型的01背包问题

首先放出AC代码：

#include<stdio.h>
#include<math.h>

int max(int a,int b);
void px(int *a);

int main()
{
    int card,n;
    while(~scanf("%d",&n),n)
    {
    int dishes[1012] = {0};
    int zeroOne[1012] = {0};
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&dishes[i]);
        }
        scanf("%d",&card);
        if(card < 5)
        {
            printf("%d\n",card);
            continue;
        }
        card -= 5;
        px(dishes);


          for(int i = 0; i < n-1 ;i++)
        {

            if(dishes[i] == 0)
                break;
            for(int j = card;j >= dishes[i];j--)
            {
                zeroOne[j] = max(zeroOne[j],zeroOne[j-dishes[i]]+dishes[i]);
            }
        }
        printf("%d\n",(card+5-zeroOne[card]-dishes[n-1]));
    }

    return 0;
}

void px(int *a)
{
    int i,j;
    int temp;
    for(i = 0;i < 1012;i++)
    {
        if(a[i]==0)
            continue;
        temp = a[i];
        j = i-1;
        while(j>=0&&a[j] > temp)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

int max(int a,int b)
{
        return a>b?a:b;

}

我认为此题的关键在于以下几点：

• 01背包算法
• 卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负）否则无法购买（即使金额足够）

所以在代码里面，我将输入情况分为金额少于5元和多于5元两种情况。

• 金额少于5元：

if(card < 5)
{
    printf("%d\n",card);
    continue;
}

• 金额多于5元

card -= 5;
px(dishes);


for(int i = 0; i < n-1 ;i++)
{

    if(dishes[i] == 0)
        break;
    for(int j = card;j >= dishes[i];j--)
    {
        zeroOne[j] = max(zeroOne[j],zeroOne[j-dishes[i]]+dishes[i]);
    }
}

当金额多于5元时，先将这5元保留，以便最后去买最贵的菜。
用减去5元之后的余下金额去做01背包
在这里，我最一开始按照我查资料得到的二维数组的方法，写出如下代码（因为存在仍然理解不透彻的原因，可能有错）：

for(int i = 0;i < count;i++ )
{
    for(int j = 0;j <= card;j++)
    {
        zeroOne[i][j] = max(zeroOne[i-1][j],zeroOne[i][j-dishes[i-1]]+dishes[i-1])
    }
}

由于还是理解不透彻，于是上网查找有关本题的滚动数组优化代码：

for(int j = card;j >= dishes[i];j--)
{
    zeroOne[j] = max(zeroOne[j],zeroOne[j-dishes[i]]+dishes[i]);
}

我觉得这个好想要更好理解一点？
其中变量zeroOne中存放的是已经花掉的金额

最后输出的时候，最终结果为：卡里面最初的总金额 - 已经花掉的金额 - 最贵那道菜的金额。

printf("%d\n",(card+5-zeroOne[card]-dishes[n-1]));