题解 P1048 【采药】
decoqwq
2017-10-23 21:01:45
`upd on 2020/2/5`:修了当年不会写的 `latex` 以及更正了部分错误
首先，这题是一道水的不能在水的题了
其次，我还是想说这题真的太水了，就是一模一样的01背包问题，输入输出都没改
就是改了一个题目背景
转化时间为背包容量和草药占的量
先讲一下二维 $dp$：
让我假设现在的背包的容量是 $C=10$；
物品编号：$ 1\ \ \ 2\ \ \ 3$
物品重量：$ 5\ \ \ 6\ \ \ 4$
物品价值：$20\ 10\ 12$
用v[i]表示物品价值，w[i]表示物品重量，要使得放入背包的物品价值最大化，我们知道用贪心是不行的！
所以接下来开始动规：
首先定义状态 $dp[i][j]$ 以 $j$ 为容量为放入前i个物品(按 $i$ 从小到大的顺序)的最大价值，那么 $i=1$ 的时候，放入的是物品 $1$ ，这时候肯定是最优的啦！
那考虑一下 $j$，$j$ 是当前容量，如果 $j<5$，那么是不是就不能放，$dp[1][j](j<5)=0$；那如果 $j>5$，就可以放了，$dp[1][j](j>=5)=20$；
接着 $i=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])$
但是好像还有一些问题没考虑完.........
看回例子：
物品编号：$ 1\ \ \ 2\ \ \ 3$
物品重量：$ 5\ \ \ 6\ \ \ 4$
物品价值：$20\ 10\ 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]$ 就好了，是不是很神奇呢！
二维 $dp$ 代码：
```cpp
#include "iostream"
#include "stdio.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;
}
```
我们再用一维dp看看，我们减掉选到哪一个物品这一维
有人就要说了，会重复放入
让我假设现在的背包的容量是 $C=10$；
物品编号：$ 1\ \ \ 2\ \ \ 3$
物品重量：$ 5\ \ \ 6\ \ \ 4$
物品价值：$20\ 10\ 12$
---------------------------------------
直接分析dp数组：
`dp：0 0 0 0 0 0 0 0 0 0`
```cpp
i=1:
dp[10] = max(dp[5]+20, dp[10]);
dp[9] = max(dp[4]+20, dp[9]);
dp[8] = max(dp[3]+20, dp[8]);
dp[7] = max(dp[2]+20, dp[7]);
dp[6] = max(dp[1]+20, dp[6]);
dp[5] = max(dp[0]+20, dp[5]);
```
`dp: 0 0 0 0 20 20 20 20 20 20`
---------------------------------------------
```cpp
i=2:
dp[10] = max(dp[6]+4, dp[10]);
dp[9] = max(dp[3]+10, dp[9]);
dp[8] = max(dp[2]+10, dp[8]);
dp[7] = max(dp[1]+10, dp[7]);
dp[6] = max(dp[0]+10, dp[6]);
```
`dp: 0 0 0 0 20 20 20 20 20 20 //看到了没，选10的都被之前的20压下去了`
-------------------------------------------
```cpp
i=3:
dp[10] = max(dp[6]+12, dp[10]);
dp[9] = max(dp[5]+12, dp[9]);
dp[8] = max(dp[4]+12, dp[8]);
dp[7] = max(dp[3]+12, dp[7]);
dp[6] = max(dp[2]+12, dp[6]);
dp[5] = max(dp[1]+12, dp[5]);
dp[4] = max(dp[0]+12, dp[4]);
```
`dp: 0 0 0 12 20 20 20 20 32 32`
-----------------------------------------
$dp[10]$ 就是背包容量为 $10$ 的时候的最大价值，就是要求的值了，可以看到，容量大的时候的值取决于容量小的时候的值，从而不断被正确更新，所以用一维 $dp$ 的时候，$j$ 的循环必须是从大到小逆序开始的，逆序，就防止了一个物品放入多次！！！否则...........
直接分析 $dp$ 数组：
`dp：0 0 0 0 0 0 0 0 0 0`
```cpp
i=1:
dp[5] = max(dp[0]+20, dp[5]);
dp[6] = max(dp[1]+20, dp[6]);
dp[7] = max(dp[2]+20, dp[7]);
dp[8] = max(dp[3]+20, dp[8]);
dp[9] = max(dp[4]+20, dp[9]);
dp[10] = max(dp[5]+20, dp[10]);
dp: 0 0 0 0 20 20 20 20 20 40 //看到问题了吗！dp[10]不仅仅是由dp[5]决定了，因为dp[5]还被dp[0]更新了一次，相当于，i=1时，即只有一个物品时，这个物品拿了两次，完全不符合01背包了，但是，这个却是我们后面要提到的完全背包！接着看：
```
---------------------------------------------
```cpp
i=2:
dp[6] = max(dp[0]+10, dp[6]);
dp[7] = max(dp[1]+10, dp[7]);
dp[8] = max(dp[2]+10, dp[8]);
dp[9] = max(dp[3]+10, dp[9]);
dp[10] = max(dp[4]+10, dp[10]);
```
`dp: 0 0 0 0 20 20 20 20 20 40`
-------------------------------------------
```cpp
i=3:
dp[4] = max(dp[0]+12, dp[4]);
dp[5] = max(dp[1]+12, dp[5]);
dp[6] = max(dp[2]+12, dp[6]);
dp[7] = max(dp[3]+12, dp[7]);
dp[8] = max(dp[4]+12, dp[8]);
dp[9] = max(dp[5]+12, dp[9]);
dp[10] = max(dp[6]+12, dp[10]);
```
`dp: 0 0 0 12 20 20 20 24 32 40`
分析完毕，之后自己想吧
重点就是，一维内层循环要倒着来！不然会重复
一维 $dp$ 代码：
```cpp
#include "stdio.h"
#include "iostream"
using namespace std;
int w[105], val[105];
int dp[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[j]=max(dp[j-w[i]]+val[i], dp[j]);
}
}
}
printf("%d",dp[t]);
return 0;
}
```