题解 GDFZOJ 【648】 多重背包

· · 个人记录

GDFZOJ原题地址戳这儿

这是一道Dp的模板题，也没什么好说的，直接开始吧

一、审题

有N件物品和一个容量为V的背包。每种物品均有有限多件，第i件物品所占空间是C_i，价值是W_i。求解将哪些物品装入背包可使价值总和最大。

数据范围：0 \le V \le 1000,0\le N\le 100,0 < C \le 1000,0 < W \le 100

似乎并没有什么关键点，粗略判断时间复杂度，emm······，O(NV)是可以过的，那就往这方面想吧

二、做题

我们发现这道题是不是和这道题、这道题很像？是的这两道题之间的差异只在这一句话\text{“每种物品均有有限多件”}，所以可以推断出这道题的式子一定和上一道题很像，所以建议先看一看上一题的题解

其实这也不是很简单吗？既然他有有限个物品，那把它转化为多个一样的物品不就做出来了吗？所以只需要在01背包的基础上再加上预处理就行啦

还不会01背包的人戳这儿

三、代码

#include<bits/stdc++.h>
using namespace std;
int weight[10001],value[10001],num[10001],f[10001];
int a,b;
int main()
{
    scanf("%d%d",&a,&b);
    for(int i=1;i<=a;++i) scanf("%d%d%d",weight+i,value+i,num+i);
    int k=a+1;
    for(int i=1;i<=a;++i)
    while(num[i]!=1)
    {
        weight[k]=weight[i];
        value[k]=value[i];
        k++;
        num[i]--;
    }
    for(int i=1;i<=k;i++)
    for(int j=b;j>=1;j--)
    if(weight[i]<=j) f[j]=max(f[j],f[j-weight[i]]+value[i]);
    cout<<f[b]<<endl;
    return 0;
}

完美撒花！！！