题解 GDFZOJ 【646】 01背包

GDFZOJ原题地址戳[这儿](http://u.gdfzoj.com/problem/646) 洛谷原模板题戳[这儿](https://www.luogu.com.cn/problem/P1048) 这是一道$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)$是可以过的，那就往这方面想吧 # 二、做题 ## 0、贪心 若果你还没学过$Dp$，就很容易会想到用**贪心**来做这道题，设一个数组$sum_i=\dfrac{W_i}{C_i}$，然后优先但是就会出现一个很大的问题：假设我们背包的容量$C=10$，有以下三个物品 |物品编号|A|B|C| |:-:|:-:|:-:|:-:| |C|6|5|5| |W|9|6|6| |Sum|1.5|1.2|1.2| 根据以上的贪心策略，我们应该是要选$A$的，但是我们发现同时选$B$和$C$的话得到的价值会更大呀，贪心思想不能从大局考虑，所以必须要用$Dp$ ## 1、背包 既然确定了是动规，那就可以愉快地开始推式子啦 让我假设现在的背包的容量C=10； |物品编号|物品重量|物品价值| |:------:|:--:|:--:| | 1 | 5 | 20 | | 2 | 6 | 10 | | 3 | 4 | 12 | 我们用$v[i]$表示物品价值，$w[i]$表示物品重量，再首先定义状态$ dp[i][j]$以$j$ 为容量为放入前$i$个物品(按$i$从小到大的顺序)的最大价值，那么 $i=1$的时候，放入的是物品$1$，这时候肯定是最优的啦！ 那考虑一下当前容量$j$，如果 $j<5$，那么肯定就不能放，所以$dp[1][j]=0(j<5)$；那如果 $j>5$，那就可以放进去了的呀，所以$dp[1][j]=20(j>=5)$； 接着 i=2i=2 放两个物品，求的就是 $dp[2][j]$ 了，当 $j<5 $的时候，是不是同样的 $dp[2][j](j<5)=0$；那当 $j<6$ 是不是还是放不下第二个，只能放第一个； 那 $j>6$ 呢？是不是就可以放第二个了呢？是可以，但是明显不是最优的，用脑子想了一下，发现 $dp[2][j](j>6)=20$，这个 $20$怎么来的呢，当然是从前一个状态来的（注意这里就可以分为两种情况了）：一种是选择第二个物品放入，另一种还是选择前面的物品； 我们假设$j=10$，这时候：$dp[2][10]=max((dp[1][10-w[2]])+v[2],dp[1][10])$也就是$dp[2][10] = max(dp[1][4])+10,dp[1][10])$ 是不是很明显了呢，$dp[1][4]+10$是选择了第二个，于是容量相应就减少成 $4$，之前已经得出 $dp[1][4]=0$，就是说选了物品$2$，物品$1$就选不了了；$dp[1][10]$是不选择第二个，只选择第一个$dp[1][10]$是等于$20$的，于是得出$dp[2][10]=20$ 到这里就可以了，依次类推，动态转移方程为 $$ dp[i][j] = max(dp[i-1][j-w[i]])+v[i],dp[i-1][j] $$ 但是好像还有一些问题没考虑完......... ## 2、需要单独考虑的问题 看回例子： |物品编号|物品重量|物品价值| |:------:|:--:|:--:| | 1 | 5 | 20 | | 2 | 6 | 10 | | 3 | 4 | 12 | 我们知道$dp[1][j](j<5)=20$，那么$dp[2][j](j=5)$的时候是多少呢？我们看到动态转移方程并没有考虑 $j<w[i]$ 的情况，但是我们可以加进去，由于我们可以看出来$dp[2][5]=5$，为什么？因为不能选第二个，只能选第一个，所以$dp[2][5]=dp[1][5]$了！所以当$j<w[i]$的时候，$dp[i][j]=dp[i-1][j]$就好了，是不是很神奇呢? ## 3、一维优化 我们刚是用二维来存状态的，那可不可以压缩到一维呢？ 答案是可以的，其实我们发现上面的$i$是可以省去的，但这个时候就会有人说了：物品会重复放入。所以重点就是，一维内层循环要倒着来！不然会重复放入 # 三、代码 ## 1、二维数组 ```cpp #include<bits/stdc++.h> using namespace std; int w[105],val[105]; int dp[105][1005]; int main() { int t,m,res=-1; scanf("%d%d",&t,&m); for(int i=1;i<=m;i++) scanf("%d%d",&w[i],&val[i]); for(int i=1;i<=m;i++) for(int j=t;j>=0;j--) if(j>=w[i]) dp[i][j]=max(dp[i-1][j-w[i]]+val[i],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; printf("%d",dp[m][t]); return 0; } ``` ## 2、一维数组 ```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]); } ``` #### 完美撒花！！！