给定储蓄罐空的和满的重量，有n种硬币，硬币有价值和重量，给出各种硬币的价值p[i]和对应的重量w[i]，求储蓄罐里面硬币的最小价值，如果没有符合要求的放硬币的方式，输出 “this is impossible”。
思路：
相当于完全背包求最小值，n中硬币对应n个物体，物体可以取无限次，存储罐里硬币重量(满罐减空罐)相当于背包的体积V。
法一：
直接扩展01背包的方程，用dp[i,v]表示取前i种硬币，存储罐重量最大为v时的最小价值。状态转移方程为：dp[i,v]=min(dp[i-1,v-k*w[i]] + k*p[i])，0<=k<= V/w[i]，取第i中硬币取k个。
递推要求N*V个状态，求每一个状态需要时间为O（v/Weight[i]），总的时间复杂度为O(NV*Σ(V/c[i]))，空间复杂度O(n2)
递推式：
for(int i=1; i<=n; ++i) for(int v=w; v<=V; ++v) for(int k=0; k*v<=V; ++k) dp[i][v] = min(dp[i-1][v],dp[i-1][v-k*w]+p*k);
法二：
1、递推代码：(对经典代码的解释)
for(int i=0; i<n; ++i) for(int j=w; j<=V; ++j) dp[j] = min(dp[j],dp[j-w]+p);
2、空间优化：
只用dp[v]即可，状态转移为：dp[v]=min(dp[v-k*w[i]] + k*p[i])，第i遍循环时，dp[i][v]只依赖于dp[i-1][v]的状态，前面的dp[0…i-1,v]都没用了，最后输出u的也是在dp[][v]里找结果，所以不用保存这些状态。这样需要保存两个dp[0][v]、dp[1][v]替换这两个变量就可以。
进一步想，k=0时，相当于dp[i][v]=dp[i-1][v]，接着枚举k都是和dp[i][v]比较的，也就是说，第i-1层循环算完后的结果相当于第i层的第一个状态，所以只需维护一个数组dp[v]就够了。
3、时间优化：
用第i个物品，即第i层循环，用dp[v-w]来更新dp[v]时，dp[v-w]已经更新过了，因为循环按照v = w to V来更新的，如下：
dp[v] = min(dp[v]未更新, dp[v-w]已更新)+p) // 更新dp[v]
= min ( dp[v]未更新, min(dp[v-w]未更新, dp[v-2w]已更新+p)+p) // 更新dp[v-w]
= min ( dp[v]未更新, dp[v-w]未更新+p, min(dp[v-2w]未更新, dp[v-3w]已更新+p)+2p) // 更新dp[v-2w]
= min ( dp[v]未更新, dp[v-w]未更新+p, dp[v-2w]未更新+2p, … , dp[v-kw]未更新+kp) // 更新dp[v-3w]
= min (dp[v-k*w]未更新+k*p) (0<=k<=V/vi)
算法复杂度：
时间复杂度O(nV)，空间复杂度O(n)
算法步骤
步骤1：读入数据，初始化dp[i]为无穷大，dp[0]=0
步骤2：递推，递推公式如上，答案就是dp[V]
代码：
#include <cstdio> #define min(a,b) (a<b)?a:b const int inf = 1e9,maxn = 8000; int dp[maxn]; int main() { int kase,V1,V ,n; int p, w; // value,weight scanf("%d",&kase); while(kase--){ scanf("%d %d %d",&V1,&V,&n); V -= V1; // init for(int i=1;i<=V; ++i) dp[i]=inf; dp[0]=0; // DP for(int i=1; i<=n; ++i){ scanf("%d %d",&p,&w); for(int j=w; j<=V; ++j){ dp[j] = min(dp[j],dp[j-w]+p); } } // output if(dp[V]==inf) printf("This is impossible. "); else printf("The minimum amount of money in the piggy-bank is %d. ",dp[V]); } return 0; }