多重背包

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn=111;int p[maxn],h[maxn],c[maxn];int dp[maxn];int main(){    int T;    scanf("%d",&T);    while(T--)    {        int n,m,i,j,k;        scanf("%d%d",&n,&m);        memset(dp,0,sizeof(dp));        for(i=1; i<=m; i++)            scanf("%d%d%d",&p[i],&h[i],&c[i]);        for(i=1; i<=m; i++)            for(j=1; j<=c[i]; j++)                for(k=n; k>=p[i]; k--)                    dp[k]=max(dp[k],dp[k-p[i]]+h[i]);        printf("%d\n",dp[n]);    }    return 0;}