背包问题的算法设计

论文总字数：31241字

目 录

1绪论 1

1.1背包问题的定义 1

1.2背包问题研究意义 1

1.3背包问题的研究历史 1

1.4本文的主要工作 1

2背包问题的经典算法 2

2.1穷举法 2

2.2贪心算法 2

2.2.1价值最高原则 3

2.2.2重量最低原则 3

2.2.3价值/重量密度最高原则 3

2.3动态规划算法 4

2.4回溯法 5

2.5分支限界法 7

3算法的设计与实现 9

3.1穷举法 9

3.2贪心算法 11

3.3动态规划算法 12

3.4回溯法 13

3.5分支界限法 14

4背包问题算法的比较 16

5总结与展望 22

5.1总结 22

5.2展望 22

参考文献 22

致谢 24

附录 25

背包问题的算法设计

赵若辰

，China

Abstract：The 0-1 Knapsack problem is a classical NP-hard problem in operations research. It has important practical significance in the aspects of resource allocation, personnel allocation, cargo loading, investment decision and so on. There are a lot of algorithms to solve Knapsack problem. For different types of algorithm, its computational efficiency and return results are quite different. There are many classical algorithms in history, such as exhaustive method, greedy algorithm, dynamic programming method, backtracking algorithm and branch and bound etc. In this work, I analyze algorithm procedure for these five algorithms. Then, combined with the characteristics of each algorithm I compare these five algorithms with others in theory. After that, I run programs to carry out numerical experiments. The conclusions are presented at the end of this paper.

Key words: Knapsack problem; a greedy algorithm; dynamic programming; backtracking; branch and bound

1绪论

1.1背包问题的定义

背包问题（Knapsack problem）是一个求最优化的经典问题。数学模型描述如下：有个物品要放入容量为c的背包，每个物品有一定的价值，但同时也会占用一定的容量，要求在不超过总容量的情况下得要最高的价值。可定义为：

其中，；表示资源编号；是第个物品的价值；为第种资源预计用量；为第个物品占第种资源量；是0-1是非选择变量(当物品被选择时=1，否则=0)。

1.2背包问题研究意义

背包问题是运筹学中的最优化问题[7]，其在资源分配，密码学，货物装载中有重要应用, 在计算机算法教学和运筹学中也多有提到[1]。也常常被作为其他优化问题的子问题加以研究。如今的网络技术迅速发展，背包问题的应用也进入到了电子商务等IT领域。特别是对于一个企业来说，资源的合理分配往往决定着公司是否能在之后的运营中有很好很快的发展，企业的资源分配一般分为人才资源分配和资金分配，而背包问题的算法可以有效的合理的进行企业资源分配，对企业的运营和发展有重要的意义。

1.3背包问题的研究历史

背包问题的应用领域广，在问题被提出之后就有大量的学者对其进行研究并获得了众多的成果。Dantzig[8]在五十年代中期就已经进行研究,开创性的利用贪心算法得出了一个最优解,即0/1背包问题最优解上界。背包问题的研究在之后的20年里没有得到突破性的进展。直到1974年,Horowitz和Sahni[9]首先利用分支限界技术开发出一算法解答背包问题,而且提出背包问题具有可分性,开创了解答该问题的一种新方法。在此之后,Martello和Toth[10]使用整数约束和分支定界技术首先改善了Dantzig的上界。1980年,Balas和Zemel[11]首次提出探讨答背包问题的“核”（Core）思想,让背包问题的研究有了很大的进展。九十年代末Pisinger[12]使用平衡技术与“核膨胀”技术设计的算法,并结合动态规划技术,又使背包问题有了较大的进展。在二十世纪的九十年代后,生物仿生技术和计算机网络技术的飞速发展,多种不同的模拟生物生活习性的算法出现,包括遗传算法，蚁群算法，蜂群算法等。

1.4本文的主要工作

本文就0-1背包问题，通过研究和分析经典背包问题经典算法，比较穷举法，贪心算法，动态规划算法，回溯法和分支定界算法等算法之间的特点，关系与优劣。编写出自己的算法，并带入实例进行论证，在对编写完成的各算法程序带入不同的数据进行对比和分析。同时对课题进行总结和展望。

本文主要分为下面几个部分：首先简单介绍了问题背景，阐述了背包问题研究意义和发展历程，并提出了本文的主要工作。然后详细介绍背包问题的经典算法，分析各个算法的性能。再自行设计算法程序解背包问题，带入实例检验。然后对自行设计的背包问题多个算法进行分析比较，总结各个算法的优劣。最后对文章总结并对背包问题的未来展望。

2背包问题的经典算法

2.1穷举法

穷举法是根据题目所给出的约束条件进行列举，把所有符合条件的可能列出来，然后在所有列出的可能中找出最优的解，穷举法因此也称作枚举法。

设这样一个0/1背包问题：背包容量为15，物品的价值集合{9, 14 , 5,10, 8}，对应重量集合{5, 8 , 2 ,6, 3}，求能装入背包的最大价值。

用穷举法，只要一一列出所有可能性。这里可以看出，由于集合中的元素没有有序的排列，列举可能项的时候会有一定的困难，可能会出现一定的混乱，所以在这里先考虑进行一个以重量为标准的降序排列，排列结束后的物品价值集合和重量集合分别为{14,10,9,8,5}，{8,6,5,3,2}。这时，经过组合得出这么几种可能（1,1,0,0,0），（1,0,1,0,1），（1,0,1,0,0），（1,0,0,1,1），（1,0,0,1,0），（1,0,0,0,1），（1,0,0,0,0），（0,1,1,1,0），（0,1,1,0,1），（0,1,1,0,0），（0,1,0,1,1），（0,1,0,1,0），（0,1,0,0,1），（0,1,0,0,0），（0,0,1,1,1），（0,0,1,1,0），（0,0,1,0,1），（0,0,1,0,0），（0,0,0,1,1），（0,0,0,1,0），（0,0,0,0,1），（0,0,0,0,0）。经过比较和取舍，最终得出最优解为（1,0,1,0,1）这时背包的最大价值为28。这是一个很精确的解，但是可以发现光是满足的情况就有如上22种，因为要列举集合元素为5个时所有可能性的组合有种，其中还有10种是经过计算发现超出背包的而舍弃的。

如果说不算大，那么把问题推广，设这样一个0/1背包问题：背包容量为C，物品价值集合为，物品重量集合为，求能放入背包的最大价值。

这时候要用穷举法举出所有的可能性有种。显然在n比较大时笔算计算量已经太大，就算交给计算机，在n上百上千的时候计算机也很难进行，不管是在时间复杂度还是空间复杂度上都存在很大压力。

2.2贪心算法

贪心算法即字面意思，做出最贪心的选择，正如小偷去偷东西，有金子银子手机水杯，必然会先装金子直到装不下或者装完了金子，再装银子手机，最后在装水杯。贪心算法为每一步做出最优的选择，但这是并不考虑到后面的选择和总体的选择。也就是说贪心算法也许并不能得到整体的最优解。贪心算法的关键是贪心策略，选择的贪心策略是一定要具备无后效性，意思是这个策略选择的结果只与当前情况有关，不顾及总体或者后续情况。

剩余内容已隐藏，请支付后下载全文，论文总字数：31241字

相关图片展示：