题目描述

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例

10

简单分析

多重背包和完全背包有所不同，完全背包是物品无限，所以我们不能将其拆解成01背包，但是多重背包的本质虽然使用次数增多，但有限，那么可操作性就很强

C++ 代码

#include <iostream>
using namespace std;
typedef long long ll;
const ll N=1e5+10;//注意数组空间要尽量开大，因为拆解背包时会扩充原有的数组大小，为了保险起见，尽量开大
ll n,m,a[N],v[N],w[N],x,y,z,t=1,sum=0;//a数组用来存放价值，v数组放体积，w数组存价值
int main()
{
    cin>>n>>m;//接下来的一个循环，我们开始对多重背包进行拆解
    for(ll i=1;i<=n;i++)
    {
        cin>>x>>y>>z;//分别对应体积，价值和数量
        sum+=z;//用来存放最终拆解后物体的总数
        for(ll j=t;j<=t+z;j++)//按次序进行将对应的数据存放到对应的数组中，上下限是t和t+z
        {
            v[j]=x;
            w[j]=y;
        }
        t+=z;//一定要让操作完的t再次加上当前物体的数量，用来对应下一批物体的标号存放到对应的数组中的位置
    }//全部操作完后之后呢，就是正常的01背包的经典操作了
    for(ll i=1;i<=sum;i++)//注意，拆解完之后物体数量为sum
    {
        for(ll j=m;j>=v[i];j--)//其余的操作不进行改变
        {
            a[j]=max(a[j],a[j-v[i]]+w[i]);
        }
    }
    cout<<a[m]<<endl;//还是输出当体积为m的时候的最优价值
}