题解 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[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 代码：

#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

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

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压下去了

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