http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1216
https://blog.csdn.net/nobleman__/article/details/78128318
多重背包

最简单的背包
Problem:1392
Time Limit:1000ms
Memory Limit:65535K
给你背包总量和物品数，以及物品的价值和体积，让你求背包装满后的最大价值

#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int vol[1200],val[1200],num[1200];
int dp[5600];
int n;
void pack01(int vol[],int val[],int v)
{
    memset(dp,0,sizeof dp);
    for(int i=1; i<=n; i++)
        for(int j=v; j>=vol[i]; j--)
        {
            dp[j] = max(dp[j],dp[j-vol[i]]+val[i]);
        }

}
void pack_all(int vol,int val,int v)
{
    for(int j=vol; j<=v; j++)
    {
        dp[j] = max(dp[j],dp[j-vol]+val);
    }
}
//int multi_pack(int vol[],int val[],int num[],int v)
//{
// memset(dp,0,sizeof dp);
// for(int i=1;i<=n;i++)
// {
// if(vol[i]*num[i]>=v)
// {
// pack_all(vol[i],val[i],v);
// }
// else
// {
// int k = 1;
// while(k<num[i])
// {
// pack01(vol[i]*k,val[i]*k,v);
// num[i]-=k;
// k<<=1;
// }
// pack01(num[i]*vol[i],num[i]*val[i],v);
// }
// }
// return dp[v];
//}
int main()
{
    int v;
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>v;

        for(int i=1; i<=n; i++)
        {
            scanf("%d",&val[i]);
        }
          for(int i=1; i<=n; i++)
        {
            scanf("%d",&vol[i]);
        }
        pack01(vol,val,v);

        printf("%d\n",dp[v]);
    }
}
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int vol[120],val[120],num[120];
int dp[56000];
int n;
void pack01(int vol,int val,int v)
{
   for(int j=v;j>=vol;j--)
   {
       dp[j] = max(dp[j],dp[j-vol]+val);
   }
}
void pack_all(int vol,int val,int v)
{
    for(int j=vol;j<=v;j++)
    {
        dp[j] = max(dp[j],dp[j-vol]+val);
    }
}
int multi_pack(int vol[],int val[],int num[],int v)
{
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
    {
        if(vol[i]*num[i]>=v)
        {
            pack_all(vol[i],val[i],v);
        }
        else
        {
            int k = 1;
            while(k<num[i])
            {
                pack01(vol[i]*k,val[i]*k,v);
                num[i]-=k;
                k<<=1;
            }
            pack01(num[i]*vol[i],num[i]*val[i],v);
        }
    }
    return dp[v];
}
int main()
{
    int v;
    while(cin>>n>>v)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&vol[i],&val[i],&num[i]);
        }
        printf("%d\n",multi_pack(vol,val,num,v));
    }
}

https://blog.csdn.net/hermann_weyl/article/details/53546874