[b]1.背包问题介绍[/b] 背包问题不单单是一个简单的算法问题，它本质上代表了一大类问题，这类问题实际上是01线性规划问题，其约束条件和目标函数如下： [img]http://files.jb51.net/file_images/article/201408/2014082811112418.jpg[/img] 自从dd_engi在2007年推出《背包问题九讲》之后，背包问题的主要精髓基本已道尽。本文没有尝试对背包问题的本质进行扩展或深入挖掘，而只是从有限的理解（这里指对《背包问题九讲》的理解）出发，帮助读者更快地学习《背包问题九讲》中的提到的各种背包问题的主要算法思想，并通过实例解释了相应的算法，同时给出了几个背包问题的经典应用。 [b]2.背包问题及应用[/b] dd_engi在《背包问题九讲》中主要提到四种背包问题，分别为：01背包问题，完全背包问题，多重背包问题，二维费用背包问题。本节总结了这几种背包问题，并给出了其典型的应用以帮助读者理解这几种问题的本质。 [b]2.101背包问题[/b] [b]（1）问题描述[/b] 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 [b]（2）状态转移方程[/b] [img]http://files.jb51.net/file_images/article/201408/2014082811112419.jpg[/img] 其中，f(i,v) 表示从前i件物品选择若干物品装到容量为v的背包中产生的最大价值。当v=0时，f(i,v)初始化为0，表示题目不要求背包一定刚好装满，而f(i,v)=inf/-inf（正无穷或负无穷）表示题目要求背包一定要刚好装满。下面几种背包类似，以后不再赘述。 [b]（3） 伪代码[/b] 从转移方程上可以看出，前i个物品的最优解只依赖于前i-1个物品最优解，而与前i-2，i-3,…各物品最优无直接关系，可以利用这个特点优化存储空间，即只申请一个一维数组即可，算法时间复杂度（O(VN)）为: 注意v的遍历顺序！！！ 下面几种背包用到类似优化，以后不再赘述。 [b]（4） 举例[/b] V=10，N=3，c[]={3,4,5}, w={4,5,6} （1）背包不一定装满 计算顺序是：从右往左，自上而下：[img]http://files.jb51.net/file_images/article/201408/2014082811112520.jpg[/img] （2）背包刚好装满 计算顺序是：从右往左，自上而下。注意初始值，其中-inf表示负无穷 [img]http://files.jb51.net/file_images/article/201408/2014082811112521.jpg[/img] [b]（5） 经典题型[/b] [1] 你有一堆石头质量分别为W1,W2,W3…WN.(W＜＝100000,N <30)现在需要你将石头合并为两堆，使两堆质量的差为最小。 [2] 给一个整数的集合，要把它分成两个集合，要两个集合的数的和最接近 [3] 有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0小于n≤30），每个物品有一个体积（正整数）。要求从n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 [b]2.2完全背包问题[/b] [b]（1）问题描述[/b] 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 [b]（2）状态转移方程[/b] [img]http://files.jb51.net/file_images/article/201408/2014082811112522.jpg[/img] 或者： [img]http://files.jb51.net/file_images/article/201408/2014082811112523.jpg[/img] [b]（3） 伪代码[/b] 注意v的遍历顺序！！！ 注意，时间复杂度仍为：O(VN). [b]（4） 举例[/b] V=10，N=3，c[]={3,4,5}, w={4,5,6} （1）背包不一定装满 计算顺序是：从左往右，自上而下： [img]http://files.jb51.net/file_images/article/201408/2014082811112524.jpg[/img] （2）背包刚好装满 计算顺序是：从左往右，自上而下。注意初始值，其中-inf表示负无穷 [url=http://files.jb51.net/file_images/article/201408/2014082811112525.jpg][img]http://files.jb51.net/file_images/article/201408/2014082811112525.jpg[/img] [/url] [b]（5） 经典题型[/b] [1] 找零钱问题：有n种面额的硬币，每种硬币无限多，至少用多少枚硬币表示给定的面值M？ [b]2.3多重背包问题[/b] [b]（1）问题描述[/b] 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 [b]（2）状态转移方程[/b] [img]http://files.jb51.net/file_images/article/201408/2014082811112526.jpg[/img] [b]（3） 解题思想[/b] 用以下方法转化为普通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中某几个数的和的形式。 该定理的证明如下： [quote] （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）的形式。 （证毕！） [/quote] 该算法的时间复杂度为：O(V*sum(logn[i])). [b]（4） 经典题型[/b] [1] 找零钱问题：有n种面额的硬币，分别为a[0], a[1],…, a[n-1]，每种硬币的个数为b[0], b[1],…, b[n-1]，至少用多少枚硬币表示给定的面值M？ [b]2.4二维费用背包[/b] [b]（1）问题描述[/b] 二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问 怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种 背包容量）分别为V和U。物品的价值为w[i]。 [b]（2）状态转移方程[/b] [img]http://files.jb51.net/file_images/article/201408/2014082811112527.jpg[/img] [b]（3）算法思想[/b] 采用同一维情况类似的方法求解 [b]（4）经典题型[/b] 有2n个整数，平均分成两组，每组n个数，使这两组数的和最接近。 [b]3.背包总结[/b] 背包问题实际上代表的是线性规划问题，一般要考虑以下几个因素已决定选取什么样的算法： （1）[b]约束条件[/b]，有一个还是两个或者更多个，如果是一个，可能是01背包，完全背包或者多重背包问题，如果有两个约束条件，则可能是二维背包问题。 （2）[b]优化目标[/b]，求最大值，还是最小值，还是总数(只需将max换成sum) （3）[b]每种物品的个数限制[/b]，如果每种物品只有一个，只是简单的01背包问题，如果个数无限制，则是完全背包问题，如果每种物品的个数有限制，则是多重背包问题。 （4）[b]背包是否要求刚好塞满[/b]，注意不塞满和塞满两种情况下初始值不同。 [b]4.参考资料[/b] dd_engi：《背包问题九讲》