文档章节

总结——01背包问题 (动态规划算法)

LoSingSang
 LoSingSang
发布于 04/10 21:27
字数 1044
阅读 177
收藏 0

0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。

问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大?

 

分析一波,面对每个物品,我们只有选择拿取或者不拿两种选择,不能选择装入某物品的一部分,也不能装入同一物品多次。

 

解决办法:声明一个 大小为  m[n][c] 的二维数组,m[ i ][ j ] 表示 在面对第 i 件物品,且背包容量为  j 时所能获得的最大价值 ,那么我们可以很容易分析得出 m[i][j] 的计算方法,

(1). j < w[i] 的情况,这时候背包容量不足以放下第 i 件物品,只能选择不拿

m[ i ][ j ] = m[ i-1 ][ j ]

(2). j>=w[i] 的情况,这时背包容量可以放下第 i 件物品,我们就要考虑拿这件物品是否能获取更大的价值。

如果拿取,m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品,背包容量为j-w[i]时的最大价值,也是相当于为第i件物品腾出了w[i]的空间。

如果不拿,m[ i ][ j ] = m[ i-1 ][ j ] , 同(1)

究竟是拿还是不拿,自然是比较这两种情况那种价值最大。

 

由此可以得到状态转移方程:

if(j>=w[i])  
    m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);  
else  
    m[i][j]=m[i-1][j];  

 

例:0-1背包问题。在使用动态规划算法求解0-1背包问题时,使用二维数组m[i][j]存储背包剩余容量为j,可选物品为i、i+1、……、n时0-1背包问题的最优值。绘制

价值数组v = {8, 10, 6, 3, 7, 2},

重量数组w = {4, 6, 2, 2, 5, 1},

背包容量C = 12时对应的m[i][j]数组。

0 1 2 3 4 5 6 7 8 9 10 11 12
1 0 0 0 8 8 8 8 8 8 8 8 8
2 0 0 0 8 8 10 10 10 10 18 18 18
3 0 6 6 8 8 14 14 16 16 18 18 24
4 0 6 6 9 9 14 14 17 17 19 19 24
5 0 6 6 9 9 14 14 17 17 19 21 24
6 2 6 8 9 11 14 16 17 19 19 21 24

(第一行和第一列为序号,其数值为0)
如m[2][6],在面对第二件物品,背包容量为6时我们可以选择不拿,那么获得价值仅为第一件物品的价值8,如果拿,就要把第一件物品拿出来,放第二件物品,价值10,那我们当然是选择拿。m[2][6]=m[1][0]+10=0+10=10;依次类推,得到m[6][12]就是考虑所有物品,背包容量为C时的最大价值。

#include <iostream>  
#include <cstring>  
using namespace std;  
  
  
const int N=15;  
  
  
int main()  
{  
    int v[N]={0,8,10,6,3,7,2};  
    int w[N]={0,4,6,2,2,5,1};  
  
  
    int m[N][N];  
    int n=6,c=12;  
    memset(m,0,sizeof(m));  
    for(int i=1;i<=n;i++)  
    {  
        for(int j=1;j<=c;j++)  
        {  
            if(j>=w[i])  
                m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);  
  
  
            else  
                m[i][j]=m[i-1][j];  
        }  
    }  
  
  
    for(int i=1;i<=n;i++)  
    {  
        for(int j=1;j<=c;j++)  
        {  
            cout<<m[i][j]<<' ';  
        }  
        cout<<endl;  
    }  
  
  
    return 0;  
}  

到这一步,可以确定的是可能获得的最大价值,但是我们并不清楚具体选择哪几样物品能获得最大价值。

另起一个 x[ ] 数组,x[i]=0表示不拿,x[i]=1表示拿。

m[n][c]为最优值,如果m[n][c]=m[n-1][c] ,说明有没有第n件物品都一样,则x[n]=0 ; 否则 x[n]=1。当x[n]=0时,由x[n-1][c]继续构造最优解;当x[n]=1时,则由x[n-1][c-w[i]]继续构造最优解。以此类推,可构造出所有的最优解。(这段全抄算法书,实在不知道咋解释啊。。)

void traceback()  
{  
    for(int i=n;i>1;i--)  
    {  
        if(m[i][c]==m[i-1][c])  
            x[i]=0;  
        else  
        {  
            x[i]=1;  
            c-=w[i];  
        }  
    }  
    x[1]=(m[1][c]>0)?1:0;  
}  

 

本文转载自:https://blog.csdn.net/xp731574722/article/details/70766804

共有 人打赏支持
LoSingSang
粉丝 3
博文 32
码字总数 6976
作品 0
深圳
程序员
私信 提问
前端与算法-动态规划之01背包问题浅析与实现

去年因为工作中的某个应用场景,需要使用到动态规划,为此花了些时间啃了啃背包算法 为啥去年的东西,今年才写粗来,也许大概是懒吧 动态规划 Dynamic Programming 先简单说下什么是动态规划...

小黎也
07/31
0
0
背包问题总结

01背包 不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前. 死亡骑士:"我要买道具!" ...

小衰哥有点帅
02/07
4
0
优秀博客推荐:各种数据结构与算法知识入门经典(不断更新)

基本算法 贪心算法:贪心算法 作者:独酌逸醉 贪心算法精讲 作者:3522021224 递归和分治:递归与分治策略 作者:zhoudaxia 图论 图的遍历(DFS和BFS): 图的遍历 作者:jefferent 最小生成...

索隆
2011/12/03
0
0
算法:Dynamic Programing

一、动态规划干嘛的 二、可以解决哪些问题 动态规划一般可分为:线性动规,区域动规,树形动规,背包动规四类。 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子...

猫咪要感冒
2016/10/09
1
0
总结——01背包问题 (动态规划算法)

0-1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。 问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? 分析一波,面对每个物品,我...

xp731574722
2017/04/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

EOS账户如何工作,我们如何获取eos账号?

EOS账户的工作方式是什么?帐户是存储在区块链中的人类可读名称。它可以由个人或一群人拥有,具体的取决于权限配置。需要一个帐户来将交易转移或推送到区块链。——EOSIO Wiki EOS账户如何工...

笔阁
12分钟前
0
0
iOS面试之@property

https://github.com/acBool/Blogs/blob/master/property/%40property%E4%BB%8B%E7%BB%8D.md @property介绍 相信做过iOS开发的同学都使用过@property,@property翻译过来是属性。在定义一个类...

壹峰
14分钟前
0
0
[springBoot系列]--springBoot注解大全

一、注解(annotations)列表 @SpringBootApplication:包含了@ComponentScan、@Configuration和@EnableAutoConfiguration注解。其中@ComponentScan让spring Boot扫描到Configuration类并把它加......

Jack088
28分钟前
7
0
tomcat编译超过64k大小的jsp文件报错原因

  今天遇到一个问题,首先是在tomcat中间件上跑的web项目,一个jsp文件,因为代码行数实在是太多了,更新了几个版本之后编译报错了,页面打开都是报500的错误,500的报错,知道http协议返回...

SEOwhywhy
49分钟前
5
0
flutter http 请求客户端

1、pubspec文件管理Flutter应用程序的assets(资源,如图片、package等)。 在pubspec.yaml中,通过网址“https://pub.dartlang.org/packages/http#-installing-tab-”确认版本号后,将http(0...

渣渣曦
50分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部