题目大意： 有一个存储罐，告诉你装满和空的重量。然后告诉你k种钱币，每种钱币的重量和对应价值，不可分。问装满这个存储罐的最小的价值是多少。
思路： 参考背包九讲。 完全背包，而且有限制，可以把dp[0]设为0，其余都是inf，若是最后dp[b-a] == inf，说明没法装满。 其实就代码来看，完全背包和01背包唯一的区别就是枚举j的顺序。 01背包的顺序是因为在选到第i件事时，dp[j]的值只能被i-1对应的比j小的值得来，所以如果由小到大更新j值，在前面dp[j]对应的是i的j，从而影响后面的值。 而完全背包就需要这个状态的dp[j],因为可以无限选。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxv = 100005; const int maxn = 505; const int inf = 0x3f3f3f3f; int w[maxn]; int v[maxn]; int dp[maxv]; int main() { int t; scanf("%d",&t); while(t--) { int a,b; scanf("%d%d",&a,&b); int n; scanf("%d",&n); for(int i = 1; i <= n ;i++) scanf("%d%d",&w[i],&v[i]); memset(dp,0x3f,sizeof(dp)); dp[0] = 0; for(int i = 1;i <= n ; i++) { for(int j = v[i]; j <= b-a; j++)//这个和01背包唯一的区别就是枚举的顺序。 { dp[j] = min(dp[j-v[i]]+ w[i],dp[j]); } } if(dp[b-a] == inf) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[b-a]); } return 0; }