题解 GDFZOJ 【647】 完全背包
zhnzh
2020-08-03 13:58:23
GDFZOJ原题地址戳[这儿](http://u.gdfzoj.com/problem/647)
洛谷原模板题戳[这儿](https://www.luogu.com.cn/problem/P1616)
这是一道$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)
在上一篇题解里我们在一维数组中说到$\text{重点就是，一维内层循环要倒着来！不然会重复}$，这是在01背包中需要做的，但是在这里就不需要了呀，反正每种物品都有无穷多件，为什么要考虑重合呢？
所以直接从小到大枚举就行啦！！！
# 三、代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int aa[1000001],bb[1000001],f[1000001];
int a,b,c,d;
int main()
{
scanf("%d%d",&a,&b);
for(int i=1;i<=b;++i) scanf("%d%d",aa+i,bb+i);
for(int i=1;i<=b;i++)
{
for(int j=aa[i];j<=a;j++)
{
f[j]=max(f[j],f[j-aa[i]]+bb[i]);
}
}
printf("%d",f[a]);
}
```
#### 完美撒花！！！