Loading...

采药 (01背包) 洛谷P1048

check评论:0 条 remove_red_eye浏览量:499 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-06

首先,这题是一道水的不能在水的题了

其次,我还是想说这题真的太水了,就是一模一样的01背包问题,输入输出都没改

就是改了一个题目背景

转化时间为背包容量和草药占的量

先讲一下二维dp:

让我假设现在的背包的容量是C=10;

物品编号: 1 2 3

物品重量: 5 6 4

物品价值:20 10 12

用v[i]表示物品价值,w[i]表示物品重量,要使得放入背包的物品价值最大化,我们知道用贪心是不行的!

所以接下来开始动规:

首先定义状态dpi以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值,那么i=1的时候,放入的是物品1,这时候肯定是最优的啦!

那考虑一下j,j是当前容量,如果j<5,那么是不是就不能放,dp[1]j=0;那如果j>5,就可以放了,dp[1]j=20;

接着i=2放两个物品,求的就是dp2了,当j<5的时候,是不是同样的dp[2]j等于0;那当j<6是不是还是放不下第二个,只能放第一个;

那j>6呢?是不是就可以放第二个了呢?是可以,但是明显不是最优的,用脑子想了一下,发现dp[2]j=20,这个20怎么来的呢,当然是从前一个状态来的(注意这里就可以分为两种情况了):一种是选择第二个物品放入,另一种还是选择前面的物品;

让我们假设一下j=10吧,可能会比较好理解!这时候:dp2 = max(dp1])+v[2],dp1);

dp2 = max(dp1)+10,dp1);

是不是很明显了呢,dp1)+10是选择了第二个,于是容量相应就减少成4,之前已经得出dp1=0,就是说选了物品2,物品1就选不了了;dp1是不选择第二个,只选择第一个dp1是等于20的,于是得出dp2=20;

到这里就可以了,依次类推,动态转移方程为:dpi = max(dpi-1])+v[i],dpi-1);

但是好像还有一些问题没考虑完.........

看回例子:

物品编号: 1 2 3

物品重量: 5 6 4

物品价值:20 10 12

我们知道dp[1]j=20,dp[2]j的时候是多少呢?我们看到动态转移方程并没有考虑j<w[i]的情况,但是我们可以加进去,由于dp2我们看出来是等于5的,为什么?因为不能选第二个,只能选第一个,所以.....dp2是不是刚好等于dp1了呢!所以当j<w[i]的时候,dpi = dpi-1就好了,是不是很神奇呢!

二维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大了,巧了,我们再用一维dp看看
一维,我们减掉有多大的j这一维

有人就要说了,会重复放入

让我假设现在的背包的容量是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

dp[10]就是背包容量为10的时候的最大价值,就是要求的值了,可以看到,容量大的时候的值取决于容量小的时候的值,从而不断被正确更新,所以用滚动数组的时候,j的循环必须是从大到小逆序开始的,逆序,就防止了一个物品放入多次!!!否则...........

直接分析dp数组:

dp:0 0 0 0 0 0 0 0 0 0

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背包了,但是,这个却是我们后面要提到的完全背包!接着看:

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

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代码:

#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;
}
好了,一道水题能分析这么多不错了,谢谢你能看到最后

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名