dp之多重背包2191

水题........

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int s[2000][2],dp[150],t[150][3];
int main()
{
    int text;
    scanf("%d",&text);
    while(text--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
        scanf("%d %d %d",&t[i][0],&t[i][1],&t[i][2]);
        int cnt=0;
        for(int i=1;i<=m;i++)
        {
            int k=1;
            while(t[i][2]-k>0)
            {
                s[cnt][0]=k*t[i][0];
                s[cnt++][1]=k*t[i][1];
                t[i][2]-=k;
                k*=2;
            }
            s[cnt][0]=t[i][2]*t[i][0];
            s[cnt++][1]=t[i][2]*t[i][1];
        }
        memset(dp,0,sizeof(dp));
        for(int i=0;i<cnt;i++)
        {
            for(int j=n;j>=s[i][0];j--)
            if(dp[j]<dp[j-s[i][0]]+s[i][1])
            dp[j]=dp[j-s[i][0]]+s[i][1];
        }
        printf("%d
",dp[n]);
    }
    return 0;
}