多重背包问题,将数量为k的物品拆分为若干组。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <climits> using namespace std; const int MAXN = 10001; int value[MAXN]; int weight[MAXN]; int dp[MAXN]; int w[MAXN]; int v[MAXN]; int k[MAXN]; int main(){ int c; cin >> c; while(c--){ int n, m; scanf("%d %d", &n, &m); int num = 0; //分解后物品的数量 for(int i = 0; i < m; i++){ cin >> w[i] >> v[i] >> k[i]; for(int j = 1; j <= k[i]; j*=2){ weight[num] = j * w[i] ; value[num] = j * v[i] ; num++; k[i] -= j; } if(k[i] > 0){ weight[num] = k[i] * w[i] ; value[num] = k[i] * v[i] ; num++; } } for(int i = 0; i <= n; i++){ dp[i] = 0; } for(int i = 0; i < num; i++){ for(int j = n; j >= weight[i]; j--){ dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } printf("%d\n", dp[n]); } return 0; }