文档章节

动态规划之0-1背包问题

一贱书生
 一贱书生
发布于 2016/11/22 10:21
字数 1415
阅读 6
收藏 1

问题描述:

现 有n件物品和一个容量为c的背包。第i件物品的重量是重量为w[i],价值是v[i]。已知对于一件物品必须选择取(用1表示)或者不取(用0表示),且 每件物品只能被取一次(这就是“0-1”的含义)。求放置哪些物品进背包,可使这些物品的重量总和不超过背包容量,且价值总和最大。

求解思路:

假 设有5件物品,其重量分别是w={2,2,6,5,4},价值分别是v={6,3,5,4,6},背包容量为10。在数学问题中这是典型的线性规划问题, 我们可以在线性约束范围内求解目标表达式。但是怎么用计算机语言实现呢?我们可以先这样考虑,当背包容量为1时,如何放置物品才能使背包中价值最大;同样 当背包容量为2时,如何放置能使背包中价值最大,以此类推,直到背包容量为10。此时我们需要维护一张二维表m[i][j],其中横坐标i表示物品,纵坐 标表示背包容量(1<=j<=10)。

                                                                                           0-1背包问题的递推二维表

                        


m[i] [j]表示当可以放入前i件物品且背包容量为j时的最大价值。当只能放入第一件物品即i=0时:若背包容量j<w[0],物品不能够被放入背包;若 j>=w[0]时,物品可以放入背包,此时m[0][j]=v[0]。当可以放入前2件物品即i=1时,我们需要进行这样的处理:若j< w[1]时,说明第2件物品不能被放入背包内,此时背包的最大价值为背包中只放入第一件物品的最大价值,即m[1][j]=m[0][j];若j& gt;=w[1]时,假设此时背包容量j=8,第二件物品可以被放入背包内,那么便会出现两种情况:

(1)将第二件物品放入背包,那么背包中物品的最大价值是多少呢?因为第二件物品重量 为w[1]=2,在将第二件物品放入背包之前,背包的容量应为j-w[1]=8-2=6,此时背包的最大价值是m[0][6],因此若将第二件物品放入背 包,其背包的最大价值m[1][j]=m[0][j-w[1]]+v[1];

(2)不将第二件物品放入背包,那么此时背包中物品的最大价值依然为只放入第一件物品时背包的最大价值,即m[1][j]=m[0][j];

我们选取(1)(2)中价值的较大者作为i=1,j=8时背包中的最大价值。

i=2,3,4时的分析同上,直到背包的容量为10,此时m[4][10]即为背包中物品的最大价值。

有了上面的分析,我们很容易写出下面的递归关系:

(1)i=0  当j<w[0]时,m[0][j]=0;当j>=w[0]时,m[0][j]=v[0]。

(2)i>0  当j<w[i],m[i][j]=m[i-1][j];当j>=w[i],m[i][j]=max{m[i-1][j-w[i]]+v[i],m[i-1][j]}。

得到了满足约束条件的背包中物品的最大价值后,需要知道是哪些物品被放入了背包。观察二维表m[i][j],我们注意到m[i][c]表示当背包重量为题目中要求的c时背包的最大价值,那么在得到m[i][c]之前,我们必然是比较了m[i-1][j-w[i]]+v[i]与m[i-1][j]的大小,从而决定是否将物品放入背包。所 以我们可以利用回溯的方法,若m[i][j]=m[i-1][j],那么物品没有放入背包;否则物品一定被放入背包。因此我们可以从最后一件物品开始,一 步一步回退到第一件物品,直到找到所有的物品放入背包的情况。本题中物品的装入情况如表中红色和蓝色部分所示,其中红色表示当前物品被装入背包,蓝色表示 没有装入背包。

代码实现:

 

[java] view plain copy

 

  1. public class Main {  
  2.     public static void main(String[] args) {  
  3.         int []w={2,2,6,5,4}; //物品重量  
  4.         int []v={6,3,5,4,6}; //物品价值  
  5.         int c=10;            //背包容量  
  6.         int []x=new int[5];  //记录物品装入情况,0表示不转入,1表示装入  
  7.         x[0]=1; //初始值表示第一个物品已装入背包  
  8.         int [][]m=new int[5][c+1];//需要维护的二维表,为了方便计算加入一列,其中第0列表示背包容量为0时背包的最大价值为0  
  9.         /* 
  10.         * 初始化第一行,即背包中装入第一件物品 
  11.         * */  
  12.         for(int j=1;j<=c;j++){  
  13.             if(j>=w[0]){  
  14.                 m[0][j]=v[0];  
  15.             }  
  16.         }  
  17.         /* 
  18.         * 背包中依次装入其他的物品 
  19.         * */  
  20.         for(int i=1;i<5;i++){  
  21.             for(int j=1;j<=c;j++){  
  22.                 if(j<w[i])m[i][j]=m[i-1][j]; //不装入背包  
  23.                 else{  
  24.                     if(m[i-1][j-w[i]]+v[i]>m[i-1][j]) m[i][j]=m[i-1][j-w[i]]+v[i]; //选择价值较大者  
  25.                     else m[i][j]=m[i-1][j];  
  26.                 }  
  27.             }  
  28.         }  
  29.         System.out.println("背包的最大价值为:"+m[w.length-1][c]);  
  30.         for(int i=4;i>=1;i--){  
  31.             if(m[i][c]>m[i-1][c]){  
  32.                 x[i]=1; //装入背包  
  33.                 c-=w[i]; //物品i装入背包之前背包的容量  
  34.             }  
  35.             else x[i]=0; //没有装入背包  
  36.         }  
  37.         System.out.print("装入背包的物品编号是:");  
  38.         for(int i=0;i<5;i++){  
  39.             if(x[i]==1) System.out.printf("%2d",(i+1));  
  40.         }  
  41.     }  

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
前端与算法-动态规划之01背包问题浅析与实现

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

小黎也
07/31
0
0
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
42
0
js算法初窥05(算法模式02-动态规划与贪心算法)

  在前面的文章中(js算法初窥02(排序算法02-归并、快速以及堆排)我们学习了如何用分治法来实现归并排序,那么动态规划跟分治法有点类似,但是分治法是把问题分解成互相独立的子问题,最...

zaking
05/29
0
0
解决最优子结构问题的两种方法----动态规划和贪心算法

1、两种重要算法思想: 动态规划,贪心算法 2、动态规划: 基本原理:动态规划英文名dynamic programming。其中pogramming指的是表格法,而非编写计算机程序。因此,可以初步得出动态规划的基...

thoresa
2015/05/18
0
0
白话版 动态规划法

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷leetcode的时候,发现了一个很不错的关于动态规划算法的例题,特来分享一下! 这是...

木子昭
01/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Ubuntu18.04 显卡GF-940MX安装NVIDIA-390.77

解决办法: 下面就给大家一个正确的姿势在Ubuntu上安装Nvidia驱动: (a)首先去N卡官网下载自己显卡对应的驱动:www.geforce.cn/drivers (b)下载后好放在英文路径的目录下,怎么简单怎么来...

AI_SKI
今天
1
0
深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
今天
1
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
今天
0
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
3
0
openJDK之sun.misc.Unsafe类CAS底层实现

注:这篇文章参考了https://www.cnblogs.com/snowater/p/8303698.html 1.sun.misc.Unsafe中CAS方法 在sun.misc.Unsafe中CAS方法如下: compareAndSwapObject(java.lang.Object arg0, long a......

汉斯-冯-拉特
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部