P244 珍惜现在，感恩生活

多重背包问题，将数量为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;
}