背包问题应用

标签: 数据结构与算法 01背包问题,完全背包问题,多重背包问题,二维费用背包问题 | 发表时间:2011-08-26 09:57 | 作者:Dong Shengbin
出处:http://dongxicheng.org

1. 背包问题介绍

背包问题不单单是一个简单的算法问题,它本质上代表了一大类问题,这类问题实际上是01线性规划问题,其约束条件和目标函数如下:
自从dd_engi在2007年推出《背包问题九讲》之后,背包问题的主要精髓基本已道尽。本文没有尝试对背包问题的本质进行扩展或深入挖掘,而只是从有限的理解(这里指对《背包问题九讲》的理解)出发,帮助读者更快地学习《背包问题九讲》中的提到的各种背包问题的主要算法思想,并通过实例解释了相应的算法,同时给出了几个背包问题的经典应用。

2. 背包问题及应用

dd_engi在《背包问题九讲》中主要提到四种背包问题,分别为:01背包问题,完全背包问题,多重背包问题,二维费用背包问题。本节总结了这几种背包问题,并给出了其典型的应用以帮助读者理解这几种问题的本质。

2.1 01背包问题

(1)问题描述

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

(2)状态转移方程

其中,f(i,v) 表示从前i件物品选择若干物品装到容量为v的背包中产生的最大价值。当v=0时,f(i,v)初始化为0,表示题目不要求背包一定刚好装满,而f(i,v)=inf/-inf(正无穷或负无穷)表示题目要求背包一定要刚好装满。下面几种背包类似,以后不再赘述。

(3) 伪代码

从转移方程上可以看出,前i个物品的最优解只依赖于前i-1个物品最优解,而与前i-2,i-3,…各物品最优无直接关系,可以利用这个特点优化存储空间,即只申请一个一维数组即可,算法时间复杂度(O(VN))为:

for i=1..N

  for v=V..0

    f[v]=max{f[v],f[v-c[i]]+w[i]};

注意v的遍历顺序!!!

下面几种背包用到类似优化,以后不再赘述。

(4) 举例

V=10,N=3,c[]={3,4,5}, w={4,5,6}

(1)背包不一定装满

计算顺序是:从右往左,自上而下:

(2)背包刚好装满

计算顺序是:从右往左,自上而下。注意初始值,其中-inf表示负无穷

(5) 经典题型

[1] 你有一堆石头质量分别为W1,W2,W3…WN.(W<=100000,N <30)现在需要你将石头合并为两堆,使两堆质量的差为最小。

[2] 给一个整数的集合,要把它分成两个集合,要两个集合的数的和最接近

[3] 有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0小于n≤30),每个物品有一个体积(正整数)。要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

2.2 完全背包问题

(1)问题描述

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

(2)状态转移方程

或者:

(3) 伪代码

for i=1..N

  for v=0..V

    f[v]=max{f[v],f[v-c[i]]+w[i]};

注意v的遍历顺序!!!

注意,时间复杂度仍为:O(VN).

(4) 举例

V=10,N=3,c[]={3,4,5}, w={4,5,6}

(1)背包不一定装满

计算顺序是:从左往右,自上而下:

(2)背包刚好装满

计算顺序是:从左往右,自上而下。注意初始值,其中-inf表示负无穷

(5) 经典题型

[1] 找零钱问题:有n种面额的硬币,每种硬币无限多,至少用多少枚硬币表示给定的面值M?

2.3 多重背包问题

(1)问题描述

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

(2)状态转移方程

(3) 解题思想

用以下方法转化为普通01背包问题:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,…,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种 物品分成系数分别为1,2,4,6的四件物品。这种方法能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示。这个很容易证明,证明过程中用到以下定理:任何一个整数n均可以表示成:n=a0*2^0+a1*2^1+…+ak*2^k,其中ak=0或者1(实际上就是n的二进制分解),

定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

该定理的证明如下:

(1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

(2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

(3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

(证毕!)

该算法的时间复杂度为:O(V*sum(logn[i])).

(4) 经典题型

[1] 找零钱问题:有n种面额的硬币,分别为a[0], a[1],…, a[n-1],每种硬币的个数为b[0], b[1],…, b[n-1],至少用多少枚硬币表示给定的面值M?

2.4 二维费用背包

(1) 问题描述

二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问 怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种 背包容量)分别为V和U。物品的价值为w[i]。

(2) 状态转移方程

(3) 算法思想

采用同一维情况类似的方法求解

(4) 经典题型

有2n个整数,平均分成两组,每组n个数,使这两组数的和最接近。

3. 背包总结

背包问题实际上代表的是线性规划问题,一般要考虑以下几个因素已决定选取什么样的算法:

(1) 约束条件,有一个还是两个或者更多个,如果是一个,可能是01背包,完全背包或者多重背包问题,如果有两个约束条件,则可能是二维背包问题。

(2) 优化目标,求最大值,还是最小值,还是总数(只需将max换成sum)

(3) 每种物品的个数限制,如果每种物品只有一个,只是简单的01背包问题,如果个数无限制,则是完全背包问题,如果每种物品的个数有限制,则是多重背包问题。

(4) 背包是否要求刚好塞满,注意不塞满和塞满两种情况下初始值不同。

4. 参考资料

dd_engi:《背包问题九讲》,available:http://www.oiers.cn/pack/Index.html

———————————————————————————————-

更多关于数据结构和算法的介绍,请查看:数据结构与算法汇总

———————————————————————————————-

原创文章,转载请注明: 转载自董的博客

本文链接地址: http://dongxicheng.org/structure/knapsack-problems/

相关 [背包问题 应用] 推荐:

背包问题应用

- Shengbin - 董的博客
背包问题不单单是一个简单的算法问题,它本质上代表了一大类问题,这类问题实际上是01线性规划问题,其约束条件和目标函数如下:. 自从dd_engi在2007年推出《背包问题九讲》之后,背包问题的主要精髓基本已道尽. 本文没有尝试对背包问题的本质进行扩展或深入挖掘,而只是从有限的理解(这里指对《背包问题九讲》的理解)出发,帮助读者更快地学习《背包问题九讲》中的提到的各种背包问题的主要算法思想,并通过实例解释了相应的算法,同时给出了几个背包问题的经典应用.

《背包问题九讲》2.0 beta1

- knighter - 崔添翼 § 翼若垂天之云
下载地址在 http://love-oriented.com/pack/pack2beta1.pdf. 全文各章语言均有更新,更新最大的章节是 3.4,提供了多重背包可行性问题的一种简明的O(VN)解法. 本文IOIFORUM首发,欢迎转载,但请保留出处.

《背包问题九讲》2.0 alpha1

- cpy - 崔添翼 § 翼若垂天之云
四年前,我曾经有过一个写一系列DP相关文章的宏伟计划,但当时这个计划仅完成了第一部《背包问题九讲》就因为我感到个人能力不足的原因中止了. 现在,我打算将这个暂命名为“动态规划的思考艺术”的文章系列重新启动. 其第一步便是用LaTeX重新修订那部广为传播并被做成过各种格式各种版本的“背包九讲”. 现在我已经完成了用LyX将九讲的原始文本输入并略加修饰的第一步,于是发布一个 alpha1 版本.

GetEd2k (Android应用)

- 某牢 - eMule Fans 电骡爱好者
GetEd2k是一个Android应用程序,作者是anacletus. 此应用可以帮助你把网页中的电驴(eDonkey) 链接添加到你个人电脑的电驴客户端里,不过前提是你的客户端开启了用于远程控制的Web interface(Web服务器,网页接口,Web界面),当然,eMule(电骡), MLDonkey 和 aMule 都支持该功能,所以这三种主流电驴客户端的用户都可以使用GetEd2k.

fixed应用

- - ITeye博客
今天在逛人人网时,发现人人网首页左侧的“应用动态”,随着我页面向下滚动,一直固定在网站的左侧. 但这效果存在一点瑕疵,在拖动过程中存在一点抖动(ie下),不是非常平滑. 我尝试使用jquey实现了该效果,也解决了抖动的问题. 创建一个ID为sideBar的div,将它的position设置为absolute.

Voldemort应用

- - 冰火岛
    互联网数据应用产品涉及到到大数据存储,譬如推荐系统,精准营销,个性化搜索这样的产品,后台离线计算的海量数据需要展示给用户. 在电子商务应用中,譬如将User作为key,给用户挖掘的结果作为value;或者以商品id作为key,商品挖掘的知识作为value,这些数据可以通过KV存储,从而满足实际需求.

httpclient4的应用

- - 编程语言 - ITeye博客
httpclient一个实现了HTTP协议的客户端编程工具包. 一个使用的背景:登录需要验证,需要压力测试一下,用webdriver等工具搞不定. 就用到了他,有ocr开源的工具,结合httpclient完美的处理了. 网上的例子主要是3的版本,这里主要是总结一下4的版本. 本身带的例子也不错:下载地址,api的参考.

Solr SpellCheck 应用

- - 开源软件 - ITeye博客
通过对各类型的SpellCheck组件学习,完成项目拼写检查功能. 本文使用基于拼写词典的实现方式,solr版本为5.3.0. SpellCheck 简述. 拼写检查是对用户错误输入,响应正确的检查建议. 比如输入:周杰轮,响应:你是不是想找 周杰伦. Solr的拼写检查大致可分为两类,基于词典与基于Solr索引.

当应用不仅仅是应用

- HACK21 - 爱范儿 · Beats of Bits
(Ankit Gupta 和 Akshay Kothari 是 Pulse 的创始人,他们的应用在 iOS/Android 平台获得极高的下载量,曾获得乔布斯的赞赏. 他们的公司 Alphonso Labs 获得了 100 万风投和天使投资). by  ankit gupta from posterous blog |  积木 译,转载请注明 ifanr 译文链接.

JMS - JMS​应​用​领​域 应用场景

- - 企业架构 - ITeye博客
Java的JMS消息类型有文本类型,对象类型,字节类型,流类型,XML类型,实际项目中,用的最多的是文本类型,对象类型和xml类型的消息.建议最好不用对象类型,因为如果用对象类型的话,调试的时候是很麻烦的,. 首先你必须要写专门的测试代码用来发送消息,. 第二,必须要管理对象所属的类的不同版本,. 第三,不方便查看queue或者topic中的消息内容..