题解 SP39 【PIGBANK - Piggy-Bank】

· · 题解

关于这道题。。。。其实就是个完全背包，这道题要求的是装满之后的最小值而不是最大值，就把max改成min，然后数组初始化的时候初始化成一个比较大的数就可以（之前初始化成二十万，结果WA到怀疑人生，在后面加个0成了二百万就AC了。。。）。 先放一下AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 2000000
using namespace std;
int T,E,F,N,P,W;
int weight[505],value[505];
int qwq[10005];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&E,&F);
        int w=F-E;
        // initialize the array
        qwq[0]=0;
        for(int i=1;i<=w;i++)   qwq[i]=INF;
        scanf("%d",&N);
        // intput the weight and value of each coin
        for(int i=0;i<N;i++)    scanf("%d%d",&value[i],&weight[i]);
        for(int i=0;i<N;i++)
        {
            for(int k=weight[i];k<=w;k++)
            {
                qwq[k]=min(qwq[k],qwq[k-weight[i]]+value[i]);
            }
        }
        if(qwq[w]>=INF) printf("This is impossible.\n");
        else    printf("The minimum amount of money in the piggy-bank is %d.\n",qwq[w]);
    }
    return 0;
}

做这道题的时候，有个比较难想的地方好弱啊，就是怎么保证这个是存满的。

如果是写个循环然后+1，貌似看起来肯定能遍历到qwq[w]这个位置从而对这个值进行min操作，看起来貌似总是能找到最小值。然后当时我就懵了不知道怎么保证找到impossible的情况。。

我们可以看一下我们的转移方程：qwq[k]=min(qwq[k],qwq[k-weight[i]]+value[i]);

由于在这个操作之前，我们把qwq数组的每一个位置都初始化成了2000000，那么，如果是impossible，那么qwq[k]和qwq[k-weight[i]]这两个位置的值都是2000000，那么对qwq[k]和qwq[k-weight[i]]+value取最小值，那肯定还是2000000。所以说qwq[w]这个位置肯定是被取过最小值，只是取了最小值之后他本身的值没变。