题解 GDFZOJ 【648】 多重背包
zhnzh
2020-08-03 14:08:53
GDFZOJ原题地址戳[这儿](http://u.gdfzoj.com/problem/648)
这是一道$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)$是可以过的,那就往这方面想吧
# 二、做题
我们发现这道题是不是和[这道题](http://u.gdfzoj.com/problem/646)、[这道题](https://www.luogu.com.cn/problem/P1048)很像?是的这两道题之间的差异只在这一句话$\text{“每种物品均有有限多件”}$,所以可以推断出这道题的式子一定和上一道题很像,所以建议先看一看上一题的[题解](https://www.luogu.com.cn/blog/zhnzh/ti-xie-gdfzoj-646-01-bei-bao)
其实这也不是很简单吗?既然他有有限个物品,那把它转化为多个一样的物品不就做出来了吗?所以只需要在01背包的基础上再加上预处理就行啦
还不会01背包的人戳[这儿](https://www.luogu.com.cn/blog/zhnzh/ti-xie-gdfzoj-646-01-bei-bao)
# 三、代码
```cpp
#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;
}
```
#### 完美撒花!!!