max Z p j x j
j 1
n w j x j c s.t. j 1 x 0,1,..., m , ( j 1,..., n) j j
有界背包问题可以转换为0-1背包问题，但转换后 并不能降低问题的求解难度。
3.无界背包问题 记pj，wj(j=1,2,…,n)分别为第j种物品的价值和 重量，第j种物品的数量没有限制，即第j种物品的数 量在理论上没有限制，c为背包总重量限制，此时的背 包问题为无界背包问题，其数学模型如下：
若不考虑预处理中排序所耗费的时间，该算法的 时间复杂度为O(n)。 该算法不能计算近似比δ ，因此属于启发式算法 没有近似程度的保障，但在该算法基础上做一点小改 动，就可得到下面介绍的近似算法。
（4）降阶法（或归约法）：通过数学论证将问题 实例中的部分变量固定在某一个值，如0-1背包可以通 过论证确定某些物品一定要装入到背包中才能取得最 优解，而某些物品一定不能装入到背包中才能取得最 优解，以此达到减小问题规模的目的，再结合其他方 法对已经降阶后的规模更小的数据实例进行求解。
数据实例分类 为测试背包算法的性能，需要对算法进行测试， 测试数据可以由计算机按某种规则自动生成。一般把 所有物品的重量限定在[1,R]之内，其中，R为正整数 生成数据时，在[1,R]内随机取一个整数作为物品j的 重量wj,然后确定数据的类型，每种数据类型对应一个 函数f(wj)，最后根据pj=f(wj)决定物品的价值pj。

按照函数f(wj),背包问题的数据实例可分为以下 几种类型： （1）无相关数据实例：无相关数据实例中每一个 物品j的价值pj和重量wj都是从[1,R]中随机取得的一 个数。每一个物品j的价值pj和重量wj之间没有相关性 物品j的价值与重量之间没有线性关系，也没有正比关 系，此时的函数f(wj)实际上是在[1,R]中取一个随机 数。 这类数据由于物品j的价值pj和重量wj之间没有相 关性，因此相对比较容易求解，分支定界法与降阶法
由此可看出，无界背包问题可以转换为有界背包 问题，又由于有界背包问题可转换为0-1背包问题，因 此无界背包问题也可转换为0-1背包问题。 4.多维背包问题 前面介绍的背包问题中，物品装入到背包中时， 背包都只有一个限制（如装入到背包中的物品总重量 不能超过背包的总载重量），这种背包问题称为一维
背包问题。若物品装入到背包中时，背包有多个限制 就称为多维背包问题，又称多约束背包问题。比如， 对背包的载重量和容积进行二维限制就变为二维背包 问题，设背包有d个限制，其限制量分别c1,c2,…,cd 记pj(j=1,2,…,n)分别为第j种物品的价值wij(i=1,2, …,d;j=1,2,…,n)分别为第j种物品的第i维属性的重 n 量，则其数学模型为：
max Z p j xij
i 1 j 1
m
n
n w j xij ci (i 1, 2,..., m) s.t. j 1 x 0,1 , (i 1, 2,..., m; j 1, 2,..., n) ij
6.子集和问题
在0-1背包问题中，令pj=wj(j=1,2,…,n)，就得 到子集和问题，其数学模型为：

（2）近似算法：给出一个算法并通过数学手段证 明该算法的近似比为δ ，从而得出该近似比下的近似 算法。 （3）动态规划法：将待求解问题分解成若干个相 互重叠的子问题，每个子问题对应决策过程的一个阶 段。一般来说，子问题的重叠关系表现为对给定问题 求解的递推关系（也就是动态规划函数），对子问题 求解一次病将解填入表中，当需要再次求解此子问题 时，可以通过查表获得该子问题的解，从而避免了大 量重复计算。
第3章
背包问题
问题概述

数学模型
背包问题（简记KP (Knapsack Problem)）是运筹
学、计算机科学中的一个典型优化难题，有着广泛的 实际应用背景，如预算控制、项目选择、投资决策、 材料切割、货物装载等，并且还常常作为其他问题的 子问题被加以研究，一般的整数规划问题都可转为0-1 问题或整数背包问题就计算复杂性而言，背包问题是 个NP难题，除非P=NP否则不存在多项式时间算法。
max Z p j x j
j 1 n
n w j x j c s.t. j 1 x 0且为整数, ( j 1,..., n) j
虽然第j种物品的数量在理论上没有限制，但实际
上由于背包总重量限制为c，因此实际上第j种物品的 装入数量最多为：
c c , 即x j为整数且0 x j wj wj
贪心算法求解0-1背包问题的步骤如下： 第一步：将各物品按单位价值由高到低排序。 第二步：去价值最高者放入背包。 第三步：计算背包剩余空间。 第四步：在剩余物品中去价值最高者放入背包。 第五步：若背包剩余容量为0或能装入的物品已全部 装入背包，则算法终止。
具体的算法伪代码可写成：
Algorithm Greedy_BKP; Begin Reduce_c:=c;{Reduce_c为背包的剩余载重量} Z_G:=0; {Z_G为背包中所有物品的总价值} For i:=1 to n do x[i]=0; For i:=1 to n do If w[i]<=Reduce_c then Begin x[i]:=1; Reduce_c:=Reduce_c-w[i]; Z_G:= Z_G+p[i]; End End

（4）反强相关数据实例：反强相关数据实例中每
一个物品j的价值pj是[1,R]中的一个随机数，重量wj= pj+R/10。 （5）几乎强相关数据实例：几乎强相关数据实例 中每一个物品j的重量wj是[1,R]中的一个随机数，价 值pj的取值范围为[wj+R/10-R/500,wj+R/10+R/500]。
j 1
n w j x j c s.t. j 1 x 0,1 , ( j 1,..., n) j
2.有界背包问题 记pj，wj(j=1,2,…,n)分别为第j种物品的价值和 重量，第j种物品的数量共有mj个，c为背包总重量限 制，此时的背包问题为有界背包问题，即每一种物品 装入到背包的数量上界为 mj个，其数学模型为： n
4.贪心算法 贪心算法是求组合优化问题的一种常用方法，其 优点是算法易于设计，执行速度快，缺点是所求得的 解不能保证最优或存在近似比，虽然对某些问题可以 证明其得到的解是最优解，如最小生成树等问题，对 有些问题，也能得出近似比，但对另一些问题，得到 的解却连近似比都没有。
贪心算法的基本思想是：将问题的求解过程看做 是一系列选择，每次选择都是当前状态下的最好选择 （局部最优解，即只注重目前的局部利益，不考虑全 局和整体的利益）。每做一次选择后，所求问题会简 化为一个规模更小的子问题，从而通过每一步的局部 解逐步到达整体解（可以是最优解，也可能不是最优 解）。


max Z p j x j
j 1
n
n w j x j c s.t. j 1 0 x 1, j (0,1,..., n) j
由于放松了原问题的约束，0-1背包问题的连续松 弛问题即为一个P问题，不难得到其最优解。令
b min j wi c i 1
（6）子集和数据实例：子集和数据实例中每一个 物品j的重量wj是[1,R]中的一个随机数，价值wj=pj。 （7）几乎相同重量的不相关数据实例：几乎相同 重量不相关数据实例中每一个物品j的重量wj是 [100000,100100]中的一个随机数，价值pj是[1,1000] 中的一个随机数。
求解算法
max Z w j x j
j 1 n
n w j x j c s.t. j 1 x 0,1 , ( j 0,1,..., n) j
常用求解技术 常用的背包问题经典求解技术（不含启发式算法） 主要有以下几种。 （1）分支定界法：通过分支来达到把问题所有可 能分成各种情况，通过计算整个问题的下界和各种分 支情况的上界来达到剪支（对目标最大化问题来说， 当一种分支情况的上界小于整个问题的下界时就把这 个分支减掉）的目的，从而减少搜索空间，获得最优 解得一种搜索方法。对于没有一般性好解法的多种问 题，分支定界法是用途很广泛的搜索方法，但不同问 题的具体实现各异，技巧性较强。
1.0-1背包问题 记pj，wj (j=1,2,…,n)分别为物品的价值和重量， c为背包总重量限制，变量
0, 不携带物品j xj ( j 1, 2,..., n) 1, 携带物品j 则0-1背包问题模型可写成如下的0-1整数线性规 n 划形式： max Z p j x j
最常见的背包问题是0-1背包问题，可描述为： 给定n个物品和一个背包，每个物品i的重量为wi， 价值为pi(i=1,2,…,n),背包能容纳的物品重量为c， 且总价值达到最大。 在0-1背包问题的基础上，对每种物品选择的数量 予以不同限定，或对背包的数量或对背包能放入的物 品进行多维限定（如对背包的载重量和容积进行二维 限制就变为二维背包问题），就会得出各种类型的背 包问题。 下面，将给出各种背包问题的数学模型。
max Z p j x j
j 1
n wij x j ci (i 1, 2,..., d ) s.t. j 1 x 0,1 , ( j 1, 2,..., n) j
5.多背包问题 若存在多个背包问题且可以把物品装入到不同的 背包中，这就是多背包问题。多背包问题中的物品数 量可以是0-1、有界、无界等各种情况，下面给出每个 物品数量是0或1的多背包问题数学模型。 记pj，wj(j=1,2,…,n)分别为物品的价值和重量 第j种物品数为1，共有m个背包，ci为第i个背包的总 重量限制，每个物品可装入任一背包内，变量为 0, 物品j不装入到背包i xij (i 1, 2,..., m; j 1, 2,..., n) 1, 物品j装入到背包i 则多背包问题的模型可写成如下形式：