完全背包问题,从前往后扫。注意和01背包的区别。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <climits> using namespace std; const int MAXF = 10001; const int MAXN = 501; const int INF = INT_MAX / 10; int value[MAXN]; int weight[MAXN]; int dp[MAXF]; int main(){ int t; cin >> t; while(t--){ int e, f, n; scanf("%d %d", &e, &f); int total = f - e; scanf("%d", &n); for(int i = 0; i < n; i++){ cin >> value[i] >> weight[i]; } for(int i = 0; i <= total; i++){ dp[i] = INF; } dp[0] = 0; for(int i = 0; i < n; i++){ for(int j = weight[i]; j <= total; j++){ dp[j] = min(dp[j], dp[j - weight[i]] + value[i]); } } if(dp[total] == INF) { printf("This is impossible.\n"); }else{ printf("The minimum amount of money in the piggy-bank is %d.\n", dp[total] ); } } return 0; }