#include<iostream>

 #include<algorithm>

 #include<stdio.h>

 #include<string.h>

 using namespace std;

 int dp[],a[],b[],c[];

 int main()

 {

     int t,n,m;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&m,&n);

         for(int i=;i<n;i++)

             scanf("%d%d%d",&a[i],&b[i],&c[i]);

         memset(dp,,sizeof(dp));

         for(int i=;i<n;i++)

             for(int j=1;j<=c[i];j++)

             for(int k=m;k>=a[i];k--)

                 if(dp[k]<dp[k-a[i]]+b[i])

                     dp[k]=dp[k-a[i]]+b[i];

         printf("%d\n",dp[m]);

     }

     return ;

 }

 在这之前，我空间好像转过一个背包九讲，现在我就只对

    01背包和多重背包有点印象了  

    先说下  背包，有n 种不同的物品，每个物品有两个属性

    size 体积，value 价值，现在给一个容量为 w 的背包，问

    最多可带走多少价值的物品。  

    int f[w+];   //f[x] 表示背包容量为x 时的最大价值

    for (int i=; i<n; i++)

        for (int j=w; j>=size[i]; j++)

            f[j] = max(f[j], f[j-size[i]]+value[i]);  

    如果物品不计件数，就是每个物品不只一件的话，稍微改下即可

    for (int i=; i<n; i++)

        for (int j=size[i]; j<=w; j++)

            f[j] = max(f[j], f[j-size[i]]+value[i]);  

    f[w] 即为所求  

    初始化分两种情况

    、如果背包要求正好装满则初始化 f[] = , f[~w] = -INF;

    、如果不需要正好装满 f[~v] = ;  

    多重背包问题要求很简单，就是每件物品给出确定的件数，求

    可得到的最大价值  

    多重背包转换成  背包问题就是多了个初始化，把它的件数C 用

    分解成若干个件数的集合，这里面数字可以组合成任意小于等于C

    的件数，而且不会重复，之所以叫二进制分解，是因为这样分解可

    以用数字的二进制形式来解释

    比如：7的二进制  =  它可以分解成    这三个数可以

    组合成任意小于等于7 的数，而且每种组合都会得到不同的数

     =  可分解成        四个数字

    如果13 =  则分解为     前三个数字可以组合成

    7以内任意一个数，加上  =  可以组合成任意一个大于6 小于13

    的数，虽然有重复但总是能把  以内所有的数都考虑到了，基于这种

    思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。  

    看代码：

    int n;  //输入有多少种物品

    int c;  //每种物品有多少件

    int v;  //每种物品的价值

    int s;  //每种物品的尺寸

    int count = ; //分解后可得到多少种物品

    int value[MAX]; //用来保存分解后的物品价值

    int size[MAX];  //用来保存分解后物品体积  

    scanf("%d", &n);    //先输入有多少种物品，接下来对每种物品进行分解  

    while (n--) {   //接下来输入n中这个物品

        scanf("%d%d%d", &c, &s, &v);  //输入每种物品的数目和价值

        for (int k=1; k<=c; k<<=1) { //<<右移 相当于乘二

            value[count] = k*v;

            size[count++] = k*s;

            c -= k;

        }

        if (c > 0) {

            value[count] = c*v;

            size[count++] = c*s;

        }

    }  

    现在用count 代替 n 就和01 背包问题完全一样了 

 #include<iostream>

 #include<algorithm>

 #include<string.h>

 #include<stdio.h>

 using namespace std;

 int dp[],a1[],b1[];//数组开大点

 int main()

 {

     int cout1,t,n,m,a,b,c,i,j,k;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&m);

         cout1=;

         for(i=;i<m;i++)

         {

             scanf("%d%d%d",&a,&b,&c);

             for(k=1;k<=c;k<<=1)

             {

                 a1[cout1]=k*a;

                 b1[cout1++]=k*b;

                 c-=k;

             }

             if(c>0)

             {

                 a1[cout1]=c*a;

                 b1[cout1++]=c*b;

             }

         }

         memset(dp,,sizeof(dp));

         for(i=;i<cout1;i++)

             for(j=n;j>=a1[i];j--)

             dp[j]=max(dp[j],dp[j-a1[i]]+b1[i]);

         printf("%d\n",dp[n]);

     }

     return ;

 }