完全背包 体积都是1000的倍数 所以可以除以1000 可能你会想价值是1000的倍数啊 这没关系
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100010; int dp[maxn]; int a[12]; int b[12]; int main() { int T; scanf("%d", &T); while(T--) { int sum, n, m, p; scanf("%d %d %d", &sum, &p, &n); for(int i = 1; i <= n; i++) { scanf("%d %d", &a[i], &b[i]); a[i] /= 1000; } while(p--) { m = sum; m /= 1000; memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { for(int j = a[i]; j <= m; j++) { dp[j] = max(dp[j], dp[j-a[i]]+b[i]); } } sum += dp[m]; } printf("%d\n", sum); } return 0; }
POJ 2063 Investment / 体积变大的完全背包,布布扣,bubuko.com
POJ 2063 Investment / 体积变大的完全背包
原文:http://blog.csdn.net/u011686226/article/details/22416393