文档章节

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

一贱书生
 一贱书生
发布于 2016/11/22 10:21
字数 1415
阅读 5
收藏 1
点赞 0
评论 0

问题描述:

现 有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
博文 722
码字总数 600072
作品 0
动态规划 &

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

Playboy002 ⋅ 2015/07/17 ⋅ 0

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

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

thoresa ⋅ 2015/05/18 ⋅ 0

贪心算法精讲

一.贪心算法的基本概念 当一个问题具有最优子结构性质时,我们会想到用动态规划法去解它。但有时会有更简单有效的算法。我们来看一个找硬币的例子。假设有四种硬币,它们的面值分别为二角五...

凡平 ⋅ 2011/10/09 ⋅ 0

白话版 动态规划法

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

木子昭 ⋅ 01/31 ⋅ 0

详解动态规划01背包问题--JavaScript实现

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

YinTokey ⋅ 05/19 ⋅ 0

XYNUOJ 1416: 竞赛总分

1416: 竞赛总分时间限制: 1 Sec 内存限制: 128 MB 提交: 12 解决: 11 [提交][状态][讨论版] 题目描述 学生在我们USACO的竞赛中的得分越多我们越高兴。 我们试着设计我们的竞赛以便人们能尽可...

dear_jia ⋅ 03/22 ⋅ 0

算法:Dynamic Programing

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

猫咪要感冒 ⋅ 2016/10/09 ⋅ 0

动态规划之01背包问题(最易理解的讲解)

01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程 f[i,j]...

暖冰 ⋅ 2016/03/31 ⋅ 0

经典动态规划题若干

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,...

樂天 ⋅ 2016/01/22 ⋅ 0

编程之美2.18——数组分割(动态规划问题)

题目概述:有一个没有排序,元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组,并使两个子数组的和最接近。(啃了好久才啃明白,主要是动态规划可惜忘了,第一眼看不懂的童鞋...

吟啸_徐行 ⋅ 2013/03/18 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Nginx服务架构初探(四):nginx服务器的rewrite功能

nginx服务器的rewrite功能 1.nginx后端服务器组的配置 1>upstream name {…} name是给服务器组限的组名 2>server address [parameters]; address为服务器地址 parame......

余温灬未存 ⋅ 今天 ⋅ 0

layer.prompt使文本框为空的情况下也能点击确定

最近一直在使用layui,但是用到弹出层layer.prompt时,如果文本框是空的话点击确定没有反应,不能向下执行。 但是我又需要空值,看看我原来的代码。 123456789 layer.prompt...

孟飞阳 ⋅ 今天 ⋅ 0

Linux普通文件压缩工具gzip、Bzip2、xz

第六章 文件压缩和打包 6.1 压缩打包介绍 Linux环境常见压缩文件类型: .zip,.gz,.bz2,.xz, .tar.gz,.tar.bz2,.tar.xz 压缩打包的目的 方便文件传输 节省磁盘空间 减少传输花费的时间 ...

弓正 ⋅ 今天 ⋅ 0

移动弹窗基础知识浅析——IOS弹窗体系

摘要: 最为常见的【弹窗】反而是最“捉摸不定”的东西。各种类型的弹窗傻傻分不清楚,不知道在什么场景下应该用哪种弹窗。尤其是遇到“二次确认”等场景…… 因此,打算从头整理移动弹窗的基...

阿里云云栖社区 ⋅ 今天 ⋅ 0

zabbix短信报警统计以及报表展示

一、需求 由于我们的业务报警比较频繁,之前是针对每个报警进行具体处理,但是有时还会重复出现,或者后续处理有时忘记跟进等,因此进行报警短信的统计,可以针对一些问题与业务跟进,明确后...

o翡翠谷o ⋅ 今天 ⋅ 0

JNI 输出LOG

1、导入log头文件。在你使用的 .c/ .cpp 文件中,导入 log.h 头文件。 #include<android/log.h> 2、在android.mk 加上 LOCAL_LDLIBS := -llog 或 LOCAL_SHARED_LIBRARIES := liblog 3、定义L......

国仔饼 ⋅ 今天 ⋅ 0

主线程pthread_exit 作用

#include <iostream>#include <pthread.h>#include <unistd.h>using namespace std;#define NUM_THREADS 10void* say_hello(void* args){ int i = *((int*)args);/......

xxdd ⋅ 今天 ⋅ 0

崛起于Springboot2.X之Mybatis-xml方式操作mysql数据库(3)

序言:当第一篇讲道Mybatis的时候,只要使用过mybatis的java程序员100%都会知道这种方式,因为这是最广泛最全面的编写sql操作mysql数据库的方式,高级sql的编写往往通过xml方式,接下来进入正...

木九天 ⋅ 今天 ⋅ 2

移动弹窗基础知识浅析——IOS弹窗体系

摘要: 最为常见的【弹窗】反而是最“捉摸不定”的东西。各种类型的弹窗傻傻分不清楚,不知道在什么场景下应该用哪种弹窗。尤其是遇到“二次确认”等场景…… 因此,打算从头整理移动弹窗的基...

猫耳m ⋅ 今天 ⋅ 0

spring elasticsearch 2.4 date 日期

1.mappingPUT user_behavior { "mappings": { "user_behavior": { "properties": { "date": { "type": "createDate", ......

xiaomin0322 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部