背包问题的进一步讨论

背包问题的进一步讨论

摘要：本文提出了背包问题的一种基于属性论的启发式算法。文章在开篇综述背包问题的一些基本情况后，接着介绍了属性论的一些基本观点、方法和理论，包括定性映射模型，人工神经元模型与定性映射模型的关系，量质转换程度函数等等。随后结合贪婪算法和背包核问题的思想，我们给出了物件基于核的一个定性映射。在根据背包的核问题的具体情况对属性论中传统的Gauss型转换程度作了必要的改进之后，我们给出了背包问题基于属性论的一个近似转化优化算法并且根据此算法用Java语言设计了背包问题软件包。软件包的设计充分结合了Java语言的特点，具有高性能和高的可扩展性，提供了可扩展的接口以方便其他应用程序扩展和调用。

关键字:背包问题，核问题，属性论方法，定性映射，转化程度函数

Knapsack problem further discussion

(Mameijuan Department of Computer Science Institute Hexi College) Abstract:After the introduction of Knapsack Problem，we focus on the basic Points，

Methods and theories of attribute theory Then, the QM of items on the basis of the Core has been introduced with the thoughts of greedy theories and core Problem theories. After the alternation of the ordinary Gauss convertion degree function, we Present an approximate algorithm based on the attribute theory. And then，a Software Package is presented in Java. The design and implementation of the Package embody many features of the Java Programming language. And the Package Can be easily extended with a good API.

KEYWORDS: knapsack Problem，Core Problem，qualitative mapping，conversion Degree function

1 引言

背包问题是一个在运筹学领域里常见的典型NP-C难题。工厂里的下料问题，管理中的资源分配，资金预算，投资决策，装载问题等均可建模为背包问题。对该问题的求解方法的研究无论是在理论上，还是在实践中都具有重要意义。对于背包问题，己有的求解方法可分为精确算法(如动态规划，分支定界等)和近似算法(如贪婪法，蚁群算法，遗传算法等)两大类。因为精确算法的时间复杂性都是呈指数增长的，所以从六十年代逐渐提出了一些近似算法。

1.1历史背景

背包问题(Knapsack problem)在50年代末期被Dantzig首次提出之后，在近年来被广泛的研究。这不仅是因为背包问题在工业和金融投资领域能得到直接的应用，更是因为很多理论上的原因。很多整数规划的问题的解决都依赖于一个高效的背包问题解法(在这些整数规划问题中，每当需要定界的时候我们都需要解决一个背包子问题，因此，一个高效的背包问题解法就显得非常有必要。

所有的背包问题都可以定性的描述为，从给定的物品集合中选择出一个子集，在不超出所有背包的负载的前提下，实现利益最大化。背包问题的不同种类的判定，是根据物品和背包的类型:在0-1背包问题(Knapsack problem)中，每一个物品最多被选择一次，而与之相对应的有界背包问题。(Bunded Knapsack problem)中能选择的物品数则可以在某个范围内取值;再比如多选择背包问题(Multi-constrained Knapsack problem)是说某几个物体必须选择一个或多个，而多背包的背包问题(Multi Knapsack problem)则是说某些背包必须同时被装满。在这些背包问题家族中，最通用的形式是多条件约束背包问题伍加(Multi-constrained Knapsack problem)，而这在实质上就是正系数的整数规划问题(Integer Programming)。在下面我们将给出各种背包问题的数学模型。

背包问题属于组合最优化问题。一般的，最优化问题(Optimization Problem)由目标函数(Objective Function)和约束条件(Constraints)两部分构成:

Minimzief(x)=f(x，，xZ，…，xn)

Subjectotx=(xl，xZ，…，xn)∈Sc x

将满足所有约束条件的解空间s称为可行域(Feasible Region)，可行域中的解称为可行解(Feasible Solution);将可行域中使目标函数最小的解称为最优解(Optimal Solution)。对于最大化问题，可将目标函数乘以(-1)转化为最小化问题求解。当x或S为离散集合构成的解空间时，这类最优化问题称为组合最优化问题(Combinatoraial Optimization problem)。

基于属性论的0-1背包问题算法研究衡量一个算法的好坏通常用算法中的加、减、乘、除和比较等基本运算的总次数同实例在计算机中计算时的二进制输入数据的大小关系来度量。我们对实例的二进制输人长度和算法的基本计算总次数是粗略估计的，一般是给予一个上限。一个求解实例I的算法的基本计算总次数C同实例I的计算机二进制输入长度d(I)的关系常用符号C(I)=f(d(I))=O(g(d(I)))表示。它的含义是:求解实例I的算法的基本计算总次数C(I)是实例输入长度d(I)的一个函数，这个函数被另一个函数g(x)控制，即存在一个函数g(x)和一个正常a使得:

C(I)≤ag(d(I))

其中g(x)的函数特性决定了基本计算总次数的性能。

定义:

假设问题和解决该问题的一个算法己经给定，如给定该问题的一个实例I，存在多项式函数g(x)，使得成立，我们称该算法对实例I是多项式时间算法;若存在g(x)为多项式函数且对该问题任意的一个实例I，都有(1-1-2)成立，则称该算法为解决该问题的多项式时间算法。

定义:

对于给定的一个优化问题，若存在一个求解该问题最优解的算法，一个多项实函数g(x)和常数a，使得对给定优化问题的任何一个实例成立，则称给定的优化问题是多项式时间可解问题，或简称多项式问题，所有多顶式问题集合记为

P(Polynomial)。

并不是所有的组合最优化问题都找到了求解最优解的多项式时间算法。也就是说，还不能肯定一些组合最优化问题是否属于P。经过几代数学家的努力，他们研究整理了一类难以求解的组合最优化问题，迄今为止，这些问题还没有一个有能求得最优解的多项式时间算法。这一类组合最优化问题归为所谓NP-hard,受人类认识能力的限制，目前人们只能假设这一类难解的组合最优化问题不存在求解最优解的多项式时间算法。

所有的背包问题都属于NP-hard问题，这就是说我们设计出背包问题的多项式时间算法的可能性非常小。也即是说对于背包问题而言，我们除了枚举整个解空间而外就无法求得背包问题的精确解。然而，下面的一些技术的应用，使得我们的枚举可能变得相对容易一些，这些技术也是目前大多数算法设计思想的一个小结:

●分枝定界，(Branch-and-bound):几乎是一个完整的枚举,只是使用上下界“剪枝”的方法避免扩展了一些不可能导出最优解的结点11011111。

●动态规划(Dyamci Porgrpmming): 动态规划的方法是在宽础上添加了一些优先规则。有的时候也可以加入边界测试，方法在某些时候可以看作分枝定界的改进版本。

●状态空间松弛(State Space Relaxatoin):在可能牺牲优化质量状态空间的大小，从而极大地减少算法的时间复杂度和空间包问题的很多高效近似解法都来源于此种思想。

●预处理(Preporcessing): 通过一些特别的测试能预先确定出在向量中某些决策变量的取值，从而事先把他们排除在外，减与其它的算法设计者类似，本文作者在算法的设计中也用到了这些思背包问题各种形式的数学模型。

1.2 背包问题各种形式的数学模型

在这些类型的背包问题中，我们用Pj表示选择物品j获得的效益品j的重量;物品需要放在承重能力为C的包裹中。同时我们还约定，所有这些系数p j,w j 和c都是正整数。

(1) 0-1背包问题(0-1 Knapsack problem)

0-1背包问题是从有n个物品的物品集选取一个子集，在总容量c的前提下，

使得相对应的利益实现最大化。可以用以下的的描述:

Maximize

j

n

j j

x p

∑=1

Subject to C

X

W n

j j

j

≤∑=1

∈

j X {0,1,…,M j }, j=1,…,n,

其中如果选择物品j 那么决策变量X j 取1，否则取。 (2) 有界背包问题[(Bounded Knapsack Problem)

物品j 最多可以选择m j 个，那么有界背包问题可以描述为:

Maximize

j

n

j j

x p

∑=1

Subject to C

X

W n

j j

j

≤∑=1

∈

j X {0,1,…,M j }, j=1,…,n,

(3) 无界背包问题 (Unbounded Knapsack problem)

无界背包问题实际上是有界背包问题的扩展，每个物品可以任意的取。 但是因为包的承重能力有限，每个物品的数目不可能取到无穷大，因此，实际上它仍旧是一个有界背包问题。

(4) 多选择背包问题 (Multi-choice Knapsack problem)

多选择背包问题是O-1背包问题的另外一种扩展。扩展不是针对数目进行的，而是针对物品的类型。也即是说，从k 类物品凡(i=I ，…，k)中选择出物品j 使得最终的总获益最大。数学定义如下:

Maximize

ij

k

i ij N j x p I

∑∑

=∈1

Subject to

C

X W

n

j ij ij

N j i

≤∑∑=∈1

x j ≥0 整数 ，j=1,..,n,

但是因为包的承重能力有限，每个物品的数目不可能取到无穷大，因此，实际上它仍旧是一个有界背包问题。

(5) 多选择背包问题 (Multi-choice Knapsack problem)

多选择背包问题是0-1背包问题的另外一种扩展。扩展不是针对数目进行的，而是针对物品的类型。也即是说，从k 类物品凡(i=I ，…，k)中选择出物品j 使得最终的总获益最大。数学定义如下:

Maximize

ij

k

i ij N j x p I

∑∑

=∈1

Subject to

C

X W

n

j ij ij

N j i

≤∑∑=∈1

∑∈i

N j ij

X

=1, i=1,…,k,

ij X ∈

{0,1}, i=1,…,k,j ∈N i

这里如果物品j 被从第i 类中选择出来，那么决策变量x ij =1。限定条件

∑∈i

N j ij

X

=1, i=1,…,k,保证了每类物品能且只能选择一个。 (6) 最大子集和问题(Subset-sum Problem)

如果0-1背包问题中每个物品的P j 都和它的W j 相等，就构成了最大子集和

问题。数学定义如下:

Maximize

j

n

j j

x p

∑=1

Subject to

C

X W

n

j j ij

≤∑=1

, i=1,...,m,

x j ≥0 整数，j=I,...n, (7) 换零钱问题 （Change-making problem)

这是一类经常碰到的问题，要从一堆具有面值w 1，w 2，…，w n 的硬币中拿出c 个货币单位的零钱找给顾客，目的是使得给出的硬币个数最少。其数学模型是:

Maximize

j

n

j x ∑

=1

Subject to

c X

W n

j j

j

=∑=1

x j ≥0 整数，j=I,…n,

(8) 多条件约束背包问题 （Multi-Constrained Knapsack problem) 在前面我们己经提到，多条件约束背包问题是背包问题的一般形式，它在形式上，就是一个正系数的整数规划问题。其数学模型如下:

Maximize

j

n

j j

x p

∑=1

Subject to

C

X W

n

j j ij

≤∑=1

, i=1,…,m,

x j ≥0 整数，j=I,…n,

以上的这些类型的背包问题无论在理论上，还是在实践中都具有非常多的应用。在理论上，背包问题是很多组合优化问题的子问题，背包问题研究上的任何一个进步都会使得这些问题的解决受益。

在实践环节上，背包问题并不局限于装箱问题。在投资问题中，某投资者用c 个货币单位去做投资，有n 个项目可供选择，其中第j 个工程的投入w j 而能获得P j 的利润。这样的投资问题就是一个0-1背包问题。

除了以上描述的简单的应用之外，背包问题还更主要的应用于货物装载，股票投资，预算控制，财务管理等问题。Diffe 和Hellman 根据最大子集和问题设计了背包公开加密算法。Martello 和Toth ，证明了计算机中双处理器任务分配问题也是一个最大子集和问题。

1.3 0-1背包问题

背包问题可以看成普通整数规划问题的特殊形式。相反的情况也是成立的，也就是说，任何一个多条件的整数规划问题都可以等价的转化为一个单条件的整数规划问题，继而转化为0-1背包问题。

我们考虑下面的整数规划问题:

Maximize

j n

j j

x p

∑=1

Subject to

C X n

j j j

=∑=111

1,

C X w

n

j j j

=∑=1

22,

0≤ x j ≤u j 整数，j=i,..n, 算法：

Maximize

j n

j j

x p

∑=1

Subject to

C X W

n

j j ij

≤∑=1

, i=1,…,m,

x j ≥0 整数，j=i,..n,

定理l-1

如果选择满足(1-3-4)的λ，那么(1-3-1)和(1-3-5)有相同的解集合。 【证明】:

很明显，对于任意的因子λ，(1-3-1)的解都将是(1-3-5)的解。因此我们只用证明相反的情况。假设x 是(1-3-5)的一个解，且令

h(x)=K (l-3-6)

很明显，K 是一个整数，因为所有的系数都是整数。我们希望证明，根据(1-3-4)选择得出的λ可以使得K=0。注意，(1-3-5)中的约束条件也可以写成:

g(x)+λh(x)=O(l-3-7)

通过代入(1-3-6)我们可以得出g(x)+λK=0.而根据(l-3-4)，有|g(x)|<λ，而且K 是整数，因此K=0.根据(1-3-6)，h(x)=0，所以g(x)=0.因此，x 是(1-3-1)的可行解。

证毕。

我们反复的应用算法1-1，就可以将多个约束转化为单个约束。对于负系数的背包问题，很容易转化为正系数背包问题。

我们还可以看出算法1-1的复杂度是线性的。因此，0-1背包问题如果得到解决，那么背包问题就能够得到解决。

1.4本文的结构和主要创新点

本论文在研究了国内外大量文献的基础上，设计了一种基于属性论的背包问题近似算法。论文主要做了如下的工作:

(1) 对背包问题的实例进行分类，并在测试过程中设计相应的实例产生策略。

(2) 结合背包的核问题和属性论的相关理论，提出物件关于核的定性映射及核的模糊化。

(3) 给出背包近似核大小的估计。

(4) 改进传统属性论中的Gauss 。型转化程度函数，以适应核问题的具体情况。

(5) 充分运用转化程度函数和贪婪算法的思想，根据国外背包算法的统计规

律，设计转化优化算法。

(6) 为算法运用Java语言设计了易于扩展的软件包。

(7 ) 用大量测试实例验证了算法的有效性。

论文的创新点主要有以下五个方面:

(1) 结合国内外背包的核问题的研究，提出物件关于核的定性映射模型。

(2) 给出近似核大小的估计。

(3) 改进传统属性论的Gauss型转化程度函数。

(4) 运用转化程度函数和贪婪算法的思想，提出了核问题产生的原因的属性论假设并根据此假设设计转化优化算法。

(5) 提供了软件包的实现。

2 0-1背包问题算法及实现

2.1 算法原理及概述

属性论方法在组合优化问题中已经得到了应用，例如谢意军将转化成度函数成功应用于问题的研究中。作为另一个应用实例，本文提出的转换优化算法是基于属性论的背包问题的新型启发式算法。

2.1.1启发式算法

启发式算法是一种技术.这种技术使得在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。

在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受或因问题的难度使其计算时间随问题规模的增加以指数速度增加，此时只能通过启发式算法求得问题的一个可行解。

早在40年代末期，由于实际问题的需要，人们已提出一些解决实际问题的快捷有效的启发式算法。随着70年代算法复杂性理论的完善，我们不再强调一定要求得到最优解，因此促使80年代初兴起的现代优化算法在今天得到了巨大的发展。

启发式算法的优点:

(1)数学模型本身是实际问题的简化，或多或少会忽略一些因素，数据采集具有不精确性，参数估计具有不准确性，以上因素可能使最优算法所得解比启发式算法所得解产生更大误差;

(2)有些难的组合优化问题可能还没有找到最优算法，即使存在，由算法复杂性理论，得知他们的计算时间是无法接受或不实际的;

(3)有些启发式算法可以用在最优算法中，如在分支定界算法中，可以用启发式算法来估界;

(4)简单易行，比较直观，易被使用者接受;

(5)速度快，在适时管理中非常重要;

(6)多数情况下，程序简单，因此易于修改。

启发式算法的缺点:

(1)不能保证求得最优解;

(2)表现不稳定，启发式算法在统一问题的不同实例计算中会有不同的效果，

有些解很好，而有些解则很差，在实际应用中，这种不稳定性造成计算结果不可信;

(3)算法的好坏依赖于实际问题、经验和设计者的技术，这一点很难总结规律，同时使不同算法之间难以比较。蚁群算法，遗传算法，和贪婪算法都属于启发式算法，在近年来的研究中，这些思想被广泛的应用于背包问题领域，并且取得了较好的效果。但是由于理论上的原因，蚁群算法，遗传算法很难充分考虑到背包问题在结构上的特点，因此，在背包问题的研究领域中，很难取得比贪婪算法更优的解。

基于以上原因，本文算法中，没有采用蚁群算法和遗传算法来求取初始解，而是采用了贪婪算法。

2.1.2 贪婪算法

在下面的讨论中，我们假设物件应经按照质价比e

j =P

j

/w

j

非递增排列，也

即是

e i e j如果 i

可能因为对象具有相同的质价比e j，使得很多序列都有这样的性质，这种情况下我们任取一个。

2.1.3 背包的核问题

背包的”核”问题是Balas和Zemel在1980年提出的，近年来国际国内几乎所有高效的背包问的算法几乎都利用了这种思想。Balas和Zemel证明了，在“核”的内部找到最优解的几率是非常高，这样就避免了考虑核外的对象，从而在规模上将背包问题变小。

在理论上，我们要找到一个背包问题的核，在难度上是和解决背包问题是一样的，也就是说找寻背包问题的精确核也是一个NP-hard，必须等到背包问题得到解决，精确核才能够找到，因此，找寻一个近似核的思想便很自然的得到了。

Balas和Zemel在1980年做了以下的试验1221:让计算机生成规模=nl000，P j 和w j均匀分布在[1，1000]的背包实例，选择c保证所有的这些背包实例的不完整项都等于500。在按照(3-1-4)完全排序之后，利用分支定界法求取此背包的最优解。他们将最优解和贪婪算法的解x’进行了比较，记录了x’有异于最优解的次数.

找到核之后，传统的方法都是对核内物件进行隐枚举或者分枝定界法去考虑，本文采取了一种新型的优化算法。算法的提出基于下面的一个假设:正是由于物件对核的转化程度的不同，才造成了背包核问题的产生。而我们的优化过程，正是对这一假设的仿真。

背包问题的近似解的满意程度

假设*X是背包问题P的最优解，那么任何其他的可行解取得的利益不可能超

过p·=X’·p(p是利益的向量)，我们假设可行解x’取得的利益为p’，那么我们很容易定义，满意解X，的满意度为:

S'x=P’/ p·

很明显，Sx.任[0，l]。

然而，由于最优解正是我们要求的，因此，我们此处根本得不到p*，因此，我们不得不改变我们的满意程度计算公式，而选择用背包的Dangiz上界替代p*，很明显，此种方法算出的满意程度S’x. S'x。如果按照此中方法得到的满意度S’'x=1，那么，很明显，此时一定找到了最优解，我们在后面的算法实现阶段要利用这个结论，作为算法最解取件的判定条件之一。

解的转换优化过程

在定义了满意程度之后，我们很容易知道，满意度越高的，一定是更好的解。我们将从贪婪解开始，运用下面的一组解转换规则进行转换，由贪婪解导出其它的可行解，如果导出解具有更好的满意度，那么我们将其记录并保留下来。

下面给出转换过程:

计算出核内每项的转化程度后，我们在目前最优解z的基础上，从不完整项开始，按照，b,b-1，b+1…，t,s:的顺序对称地向两侧进行转换运算，其中，第i项转换为1-x i的概率就选择为p i，这些我们取得z’，此时的z’不一定是可行解，因此，我们进行下面的处理，处理的方法仍旧应用了贪婪策略:

(l)计算当前的总重量w’;

(2)如果w’超过。，则另建数组，将核内未选择项按e i(从小到大)进行排序。

从左向右扫描该数组，从背包中取出对象，直到当前记交;

(3)如果w’不足。，则另建数组，将核内未选择项按e i(从大到小)进行排序。

从左向右扫描该数组，继续填充背包;

(4)计算此时可行解的满意度，如果比目前最好解得满意度高，则用新的z’替代z;

(5)重复以上过程，直到算法使用者终止为止或者最大满意度为1。

2.2 算法设计

2.2.1 算法整体流程

图2.2.1 算法整体流程

整个处理过程可以分为四个阶段，它们按流程顺序依次是数据预处理，求初始可行解，计算近似核的大小及核内每点转化程度以及循环优化阶段。

2.2.2 数据预处理

根据背包问题设计原理，为了减小不必要的运算，本算法对数据也进行了预处理。数据预处理的工作很简单，就是从可选择物件中去除那些weight己经大于

背包容量的对象。同时，累加其余物件的w i和∑i w。如果∑i w≤c。，那么选中所有对象，并返回，算法结束，预处理过程只需一次扫描对象即可完成。

此过程流程图算法流程图为:

图2.2.2预处理过程流程图

2.2.3 求取初始可行解

采取贪婪算法求取初始可行解。算法如下:

(l)初始化数组，将对象按照e i，不减的顺序进行排序，排序算法采用二分归并排序或者快速排序法，使得排序时间为O(nlogn)。

(2)从左到右扫描数组，开始选择物件，直到当前物件的重量大于背包剩余容量cr为止，记忆当前对象的下标为b，计算背包的Dnazgi上界，以用于求可行解的满意度。

(3)登记此时的选中状态，X所得效益Pt，以及背包剩余容量rc为初始可行解。如果cr=0，那么此时己得到最优解，返回结果，算法结束，否则执行下一步骤。

求取初始可行解的算法流程图为:

图2.2.3取得初始可行解算法流程

2.2.4 找寻近似核和计算核内各点的转化程度

根据背包问题的p，n和w计算背包问题的核的大小的近似值，计算方法见以上公式。

根据核的大小以及核内对象的下标与b的距离，计算核内每个对象的转化程度。计算公式见以上公式。.

2.2.5 循环转化优化过程

后面就是我们循环优化的过程。由于本算法是一个启发式算法，因此它也具有启发式算法的特点，算法无法确定当前是否为最优解(除了一种特殊情况之外)。和其它的核算法一样，本算法也只讨论核内的物件进行优化，而不去考虑核外的物件。下面给出每一轮循环的优化过程:

(l)从左向右，对核内的对象的选中状态(就是背包解)xi按照各自的转化程

，转化。直到核内所有物件转化完为止。计算此时背包的剩余承重rc。度朝1-x

i

(2)如果rc

(3)如果cr>0，运用贪婪策略，依次扫描核内的物件，增加还能增加进入背

包的物件。

(4)比较此时的解与当前最优的结果，如果此时的解更好，那么记录当前的解。

(5)恢复贪婪解状态，进入下一轮循环。

3 算法测试结果分析

3.1 测试结果

我们对以下实例分别进行了测试，程序的优化速度都很快。尤其是传统的分枝定界法难于处理的强相关实例和最大子集和实例，本算法的优化非常成功。我们选择的测试实例是这样产生的:界于l-3000，n分别等于10000，30000，50000和100000，背包容量Capacipy都定为重量和的1/2，对于p的产生策略根据实例类型的不同而不同，我们在下面的测试结果部分表述。

下面将列表给出以下结果:

(1)不相关处理结果

设p随机产生于1-3000，下面是取得各次测试取得满意度为99.7%所耗费的计算时间，单位毫秒(ms):

设置p随机产生于[w-300，w+300],如果p<=0，那么令P=l下面是取得各次测试取得满意度为99.7%所耗费的计算时间，单位毫秒 (ms):

3.2 结果分析

上面所列的测试结果只是我们测试中的一部分。根据上面的测试数据，我们可以看出，本算法是比较稳定的，对于同一种类型的实例，取得较满意解的时间相差不大。并且对于四种实例大多数情况下都能在较短的时间内取得很高的满意度 (99.7%)。

实际生活中，特别是在投资领域，决策者经常需要对投资很快的作出反应，否则机会稍纵即逝。这种情况下，本算法一定具有非常宽广的应用前途。

4 结论

本文提出的基于属性论的0-1背包问题的近似解法属于启发式算法的一种。根据实验结果分析，程序收敛很快，能够处理传统的方法不能处理的多维背包的问题。处理的结果也非常好，对于最难处理的最大子集实例，算法能很快地求出能够接受的可行解。在实际的生活中，往往需要决策者在很短的时间内给出方案的一个好的可行方案，在精确解法无法完成任务的情况下，本算法势必有重要的应用性。

5 前景与展望

背包问题的研究起源于旅行者携带用品的背景，要求在旅行袋容积有一定限制的条件下，所携带物品的总价值最大。同时，背包问题也可以理解为在资源有限的情况下，如何分配资源使得收益最大。现在，许多问题都可以建模为背包问题，如工厂里的下料问题，管理中的资源分配，资金预算，投资决策，装载问题等。这类问题在海运、空运等领域中有重要的应用。所有的0-l整数规划问题都可以看成是背包问题来进行求解，而所有的整数规划问题都可以转化为O-1整数规划问题。求解背包问题实际上就求解了所有的整数规划问题，所以对该问题的求解方法的研究无论是在理论上，还是在实践中都具有一定的应用前景。

参考文献

[1] 王晓东.算法设计与分析[M].清华大学出版社；北方交通大学出版社，2003．

[2] 姚瑞枫，多维0-1背包问题的遗传算法研究，武汉科技大学硕士学位论文，2003.

[3] 郑杨凡，冯嘉礼等，”背包问题的一种新型近似解法”.

[4] 玄光男，程润伟，遗传算法与工程优化[M]，清华大学出版社，2004.

[5] 杨千里，王育民，电子商务技术与应用，[M]．北京：电子工业出版社，1999．

[6] 邢文训，谢金星.现代优化计算方法.1999，清华大学出版社.

[7] 姜灵敏,陈松乔.二重结构编码遗传算法及其在贷款组合优化决策中的应用[J].型微型

计算机系统,2004,25(7):

[8] 马良等.背包问题的蚁群优化算法[J].计算机应用.2001, 21(8):4-5.

[9] 邱菀华,冯允成,魏法杰,等.运筹学教程[M].北京:机械工业出版社,2004:24-25.

[10] Ladleman1 Molecular computation of solutions to combinatorial problems [J]1

Science,1994,266:1021-1024.

[11] PisingerD.Aminimal algorithm for the 0-1 knapsack problem [J].Operation

Research, 1997,45:758-767.