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-一个物件最优解，而与前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的解析xml次序！！！
下边几类挎包采用相近提升，之后不会再过多阐释。
（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] 给一个整数金额的结合，要把它分为2个结合，要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]};
[/cpp
留意v的解析xml次序！！！
留意，算法复杂度仍为：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个整数金额，均值分为2组，每一组n数量，使这2组数的和最贴近。
3. 挎包小结
背包问题事实上意味着的是线性规划问题难题，一般要考虑到下列好多个要素已决策选择哪些的优化算法：
（1） 约束，有一个還是2个或是更好几个，如果是一个，可能是01背包，完全背包或是多重背包难题，如果有2个约束，则可能是二维背包问题。
（2） 提升总体目标，求最高值，還是极小值，還是数量(只需将max换为sum)
（3） 每个物件的数量限定，假如每个物件只有一个，仅仅简易的01背包难题，假如数量无限制，则是完全背包难题，假如每个物件的数量有限定，则是多重背包难题。
（4） 挎包是不是规定恰好装满，留意不装满和装满二种状况下初值不一样。
4. 参考文献
dd_engi：《背包问题九讲》，available：http://www.oiers.cn/pack/Index.html
