在解决完全背包问题时，通常会遇到两种问题，一种是恰好将背包装满，一种是不要求恰好装满。是否恰好装满只是初始化的会有区别。
恰好装满 如果要求恰好装满背包，那么在初始化时除了f[0]为0，其它f[1..V]均设为-∞（求最小值设为∞），这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
不一定恰好装满 如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了（转自军魂）
另一种是完全背包的最值问题，一种是求最小值，一种是求最大值。恰好填满求最大值，初值设置为-∞；求最小值设为∞；不要求恰好填满就是设置为0。然后是在贪心的时候策略问题，最大选用max( ),最小选用min( ).
题意：一个存钱罐空和满的时候重量分别为E,F，给出N种硬币的价值p[i]和重量w[i]，求使存钱罐达到F重量使用的硬币总价值最小为多少。
数据范围：1 <= E <= F <= 10000，1 <= N <= 500，1 <= P <= 50000, 1 <= W <=10000
可以转化为把背包填满，需要的最小花费。一个完全背包问题，但是求最小价值，不是最大价值。
复杂度：一重for循环枚举N种物品，一重for枚举V=F-E，O(N*F)=O(5e6)，可做。
因为恰好填满求最小值，初始值d[0]=0,f[1…maxn]设置为∞.然后f[v]!=∞,有解，否则无解。
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int maxn=505,maxm=1e4+5; const int INF=0x3f3f3f3f; int p[maxn],w[maxn]; int f[maxm]; int main() { int t; scanf("%d",&t); int E,F; while(t--) { scanf("%d%d",&E,&F); int v=F-E,n; scanf("%d",&n); for(int i=1; i<=n; ++i) scanf("%d%d",&p[i],&w[i]); memset(f,INF,sizeof(f)); f[0]=0; for(int i=1; i<=n; ++i) { for(int j=0; j<=v; ++j) { if(j>=w[i]) f[j]=min(f[j],f[j-w[i]]+p[i]); } } if(f[v]!=INF) printf("The minimum amount of money in the piggy-bank is %d.\n",f[v]); else printf("This is impossible.\n"); } return 0; }