题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1114
题意是有一个存钱罐，当它是空的时候重量为E，满的时候重量为F；已知存钱罐里面有 n 种钱，每种钱的价值为 P 重量为 W ；求存钱罐满的时候里面至少有多少钱；
是一个完全背包(求从n个物品中选出总重量不大于W的最大价值)问题：
二维数组：
(1 <= i <=n; 0<=j<=W)
dp[i][j] = max( dp[i-1][ j], dp[i][ j-w[i] ]+v[i] )(j>=w[i]);
=dp[i-1][j];(j<w[i]);
一维数组：
（1<=i<=n; w[i]<=j<=W）
dp[j]=max( dp[j], dp[ j-w[i] ]+v[i] );
而本题求得是最小价值所以稍微改一下就可以了
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; #define N 50100 #define INF 0xfffffff int dp[N], v[N], w[N], W, n; int main() { int T, E, F; scanf("%d", &T); while(T--) { scanf("%d %d", &E, &F); W = F - E; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d %d", &v[i], &w[i]); for(int i=0; i<=W; i++) dp[i]=INF; dp[0]=0; for(int i=1; i<=n; i++) { for(int j=w[i]; j<=W; j++) { dp[j]=min(dp[j], dp[j-w[i]]+v[i]); } } if(dp[W]==INF) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[W]); } return 0; }
原文：http://www.cnblogs.com/zhengguiping--9876/p/4919659.html
