文档章节

动态规划之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

没有更多内容

加载失败,请刷新页面

加载更多

python:关于读取文件的指定行的问题

先来造一个文件:就叫做 test.txt吧,内容是下面这个样子: 表头1,数据12,数据23,数据34,数据45,数据56,数据67,数据7 那么我们并不打算把这个表头给读出来 怎么办呢? 先来打开文...

Oh_really
12分钟前
1
0
Rails 用现代 Rails 逃离单页面应用 “兔子洞”

在工作共总是觉得turbolinks非常爽,但是却总是被说成是过时的技术,大家都喜欢spa,哪怕不用的spa的人也是禁用掉的多,找不到很好的理由劝说别人使用,这篇文章说的很到位,或者说至少是牛人...

wmzsonic
17分钟前
0
0
Hive 分布式搭建,Spark集成Hive记录

本帖详细介绍搭建步骤,仅仅记录自己搭建过程以及采坑经历。 前提环境: Hadoop集群 版本2.7.2 Spark集群 版本2.1.0 Linux版本 Centos7 准备搭建 MySql版本5.5.61 ,Hive-2.1.0 去官网下载M...

我爱春天的毛毛雨
19分钟前
1
0
打包QML程序

1、windeployqt执行路径(D:\Qt\5.12.0\msvc2017_64\bin)加入到PATH中 2、使用Qt自带的命令行交互 Command 终端(Qt 5.12.0 64-bit for Desktop (MSVC 2017))切换到 Release 编译成功的exe...

渣渣曦
56分钟前
4
0
优秀互联网高级测试工程师应该具备的能力

概述 在之前写的互联网高级测试工程师至少具备的能力一文中,提到了测试工程师至少具备的能力,但是并没有提到优秀测试工程师应该具备的能力,下文简单的谈一谈。当然这些全部都是我的个人理...

Sam哥哥聊技术
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部