Piggy-Bank 原文在这里
经典完全背包问题,这里采用o(VN)算法,与01背包的区别仅仅是 v 从0-V递增,这样每一种就可以取多次
这一题需要注意的有两点1.求的是最小和 2.背包要装满
第一个问题只需把MAX改成MIN即可
第二个问题 让dp[0]=0 其他都初始化成正无穷,这样就可以区分出 是不是恰好装满(dp[v]是正无穷表示没装满,否则装满)
#include <stdio.h> #include <string.h> #define M 100000000 #define MIN(a,b) (a)>(b)?(b):(a) int main() { int t,e,f,v,n,p[502],w[502],dp[10002]; scanf("%d", &t); for (int k = 0; k < t; k++){ memset(p, 0, sizeof(p)); memset(w, 0, sizeof(w)); scanf("%d%d", &e, &f); v = f - e; scanf("%d", &n); dp[0] = 0; for (int i = 1; i <= v; i++){ dp[i] = M; } for (int j = 0; j < n; j++){ scanf("%d%d", &p[j], &w[j]); } for (int i = 0; i < n; i++){ for (int j = w[i]; j<=v; j++){ dp[j] = MIN(dp[j], dp[j - w[i]] + p[i]); } } if (dp[v] >= M){ printf("This is impossible.\n"); } else{ printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]); } } return 0; }