悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

  直接套用多重背包模板即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define mst(a,b) memset(a,b,sizeof(a))
const int maxn=1e4+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int v[105],val[105],k[105];
int dp[105];
void zero_one(int cost,int val,int vtot)
{
    for(int j=vtot;j>=cost;j--)
        dp[j]=max(dp[j],dp[j-cost]+val);
}
void complete(int cost,int val,int vtot)
{
    for(int j=cost;j<=vtot;j++)
        dp[j]=max(dp[j],dp[j-cost]+val);
}
void multiple(int cost,int val,int num,int vtot)
{
    int k=1;
    if(cost*num>=vtot)
    {
        complete(cost,val,vtot);
        return ;
    }
    while(k<num)
    {
        zero_one(k*cost,k*val,vtot);
        num-=k;
        k<<=1;
    }
    zero_one(num*cost,num*val,vtot);
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {    
        mst(dp,0);
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
            cin>>v[i]>>val[i]>>k[i];
        for(int i=1;i<=m;i++)
            multiple(v[i],val[i],k[i],n);
        cout<<dp[n]<<endl;
    }
    return 0;
}