文档章节

动态规划之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
详解动态规划01背包问题--JavaScript实现

一开始在接触动态规划的时候,可能会云里雾里,似乎能理解思路,但是又无法准确地表述或者把代码写出来。本篇将一步一步通过作图的方式帮助初次接触动态规划的同学来理解问题。这一篇将以经典...

YinTokey
05/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Security 实现 antMatchers 配置路径的动态获取

1. 为什么要实现动态的获取 antMatchers 配置的数据 这两天由于公司项目的需求,对 spring security 的应用过程中需要实现动态的获取 antMatchers ,permitAll , hasAnyRole , hasIpAddre...

大木老师故事的小黄花
16分钟前
19
0
Java 内存模型

一、Java内存模型 硬件处理 电脑硬件,我们知道有用于计算的cpu、辅助运算的内存、以及硬盘还有进行数据传输的数据总线。在程序执行中很多都是内存计算,cpu为了更快的进行计算会有高速缓存,...

微笑向暖wx
17分钟前
0
0
Maven shade的使用

有时你的工程里会和你的Spark环境出现包冲突,这时候可以用Maven shade将你的包名重命名,在maven里加上: <plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-shade......

守望者之父
18分钟前
0
0
SpringBoot中导入Excel的总结

1 先导入配置文件 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId></dependency><dependency><groupId>org.apache.poi</groupI......

小小小施爷
18分钟前
0
0
python是如何进行内存管理的

Python引入了一个机制:引用计数。 python内部使用引用计数,来保持追踪内存中的对象,Python内部记录了对象有多少个引用,即引用计数,当对象被创建时就创建了一个引用计数,当对象不再需要...

糖宝lsh
21分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部