数据结构背包问题的求解

1、德州学院 物理系 2009届 电子信息科学与技术专业 数据结构课程设计背包问题的求解摘 要 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。关键词 背包问题； 递归算法1问题描述1.1问题描述背包问题是一种组合优化的NP完全问题。问题可以描述为：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最

2、大。它主要分为以下几种问题： （1）0/1背包问题有n件物品和一个容量为v的背包。第i件物品的重量是ci，价值是wi。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。(2)完全背包问题有n种物品和一个容量为v的背包，每种物品都有无限件可用。第i种物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 这个问题非常类似于0/1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件等

3、很多种。（3）多重背包问题有n种物品和一个容量为v的背包。第i种物品最多有n件可用，每件体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n+1种策略：取0件，取1件取 n件。各类复杂的背包问题总可以变换为简单的0/1背包问题。本次课程设计主要研究0/1背包问题的求解。1.2基本思想0/1背包问题的求解是一个很经典的案例。对于它的分析与研究已经到达了一定的深度，解决这个问题有很多很多的办法。其中比较常用的有以下几种方法： （1）回溯法回溯法的主要思想：

4、首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出放弃，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，因此要用到栈。（2)贪心法根据贪心的策略，每次挑选价值最大的物品装入背包，判断得到的结果是否最优；每次挑选所占重量最小的物品装入，判断是否能得到最优解；每次选取单位重量价值最大的物品，判断是否能得到最优解。（3

5、） 递归法 此法是穷举法的改进，利用递归函数依次选择每个物品，直到求出最优解。分析比较以上各种方法，回溯法利用栈，程序较复杂；贪心法的最终结果不一定是最优解；递归方法是比较简化程序的一个方法，且比较容易理解。故本次课程设计选择利用递归法求解0/1背包问题。递归法的基本思路为：（1） 分别输入n件物品的重量和价值。（2） 采用递归寻找物品的方案。（3） 输出最佳的装填方案：包括选中的是哪几种物品，总价值为多少。2问题分析 设n件物品的重量分别为w0,w1,wn-1,物品的价值分别为v0,v1,vn-1。采用递归寻找物品的选择方案。设前面已经有了多种选择方案，并保留了其中最大的选择方案于数组opt

6、ion,设方案的的总价值存于变量maxv,当前正在考察新方案其物品选择情况保存于数组cop，假定当前方案已经考虑了前i-1件物品，现在正在考虑第i件物品；当前方案已经包含的物品的质量之和为tw;至此，若其余物品都选择可能的话，本方案能达到的总价值的期望值设为tv，算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会再被考察。这同时保证函数后找到的方案一定会比前面的方案更好。对于第i件物品的选择有两种可能：（1）物品i被选择，这种可能性仅当包含它不会超过

7、方案总重量的限制时才是可行的。选中后，继续递归去考虑其余物品的选择；（2）物品i不被选择，这种可能性仅当不包物品i也有可能会找到价值更大的方案的情况。就此，通过不断地对从第一件开始的物品到第n件物品进行选择或是不选择，从而从各个方案的比较中选择出最优方案。采用option和cop两个数组，来辅助完成递归寻找物品的选择方案。数组option起到一个“旗帜”作用，用来区别于未被选择的物品，从而达到输出被选择的函数。而cop则像是一个中间变量，它在递归过程中不断地发生变化，将有效的最终数据传输给数组option，起到一个“桥梁”作用。3数据结构描述背包问题结构体：struct int weight;

8、 /*物品的重量*/int value; /*物品的价值*/aN;4算法设计4.1程序流程图图4-1 程序流程图4.2算法设计根据问题分析中的思想写出递归算法如下：find（物品i，当前选择已达到的重量和tw,本方案可能达到的总价值为tv） /*考虑物品i包含在当前方案中的可能性*/ if（包含物品i是可接受的）将物品i包含在当前方案中； if(i<n-1)find(i+1,tw+物品i的重量,tv)；else/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/ 以当前方案作为临时最佳方案保存； 恢复物品i不包含状态； /*考虑物品i不包含在当前方案中的可能性*/ if（不包含物

9、品i仅是可考虑的）if(i<n-1)find(i+1,tw,tv-物品i的价值)；else/*又一个完整方案，因它比前面的方案好，以它作为最佳方案*/ 以当前方案作为临时最佳方案保存； void find(int i,int tw,int tv) int k;if(tw+ai.weight<=limitw) /*物品i包含在当前方案的可能性*/ copi=1;if(i<n-1)find(i+1,tw+ai.weight,tv);elsefor(k=0;k<n;k+)opionk=copk;maxv=tv;copi=0;if(tv-ai.value>maxv) /*

10、物品i不包含在当前方案的可能性*/if(i<n-1)find(i+1,tw,tv-ai.value);elsefor(k=0;k<n;k+)opionk=copk;maxv=tv-ai.value;5详细程序清单详细程序清单见附录。6程序运行结果背包问题求解界面如图6-1所示。图6-1 背包问题求解界面程序调试成功。在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号像“；”也很容易丢掉或是中英文格式不正确；甚至像0和 O这种小错误有时也会发生，在经过调试和完善程序的过程中，这些错误已经全部改正。在此过程中我们学到了不少调试的技巧，极大得丰富了编程

11、的知识，这些在程序的优化方面帮助很大。7心得体会通过此次课程设计的实践，感触较深。不仅使我们加深了对书本知识的理解，而且锻炼了我们编写程序、调试程序的能力。同时，此次课程设计也充分弥补了课堂教学中知识的缺陷。这次课程设计由于时间有限，对有些地方考虑的还不够周到。在本课题中，我们研究了如何用递归算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。所以我们试着用所学的数据结构知识以及递归法来解决普通的背包问题。背包问题的递归思想确实有点难以理解，为了理解这个思想，我们确实花了很长时间，不过很高兴最后经过我们的讨论掌握了这个

12、思想。参考文献1 徐孝凯. 数据结构课程实验. 北京：清华大学出版社，2002:100-1322 张乃笑. 数据结构与算法. 北京：电子工业出版，2000:3-53 严蔚敏. 数据结构（C语言版）. 北京： 清华大学出版社，2002:100-1324 李春葆. 数据结构（C语言篇）习题与解析（修订版）. 北京：清华大学出版，2000:45-66 Knapsack problem solvingLi Shuai Zhu Zhili Kong Rongrong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combi

13、natorial optimization problem solving method has become the focus of attention of the scientific.It not only lies in its inherent complexity that has important oretical value, but also that they can be used in real life widely. Knapsack problem is a typical combinatorial optimization problem. The co

14、urse is designed to use recursion algorithm for solving knapsack problem which is under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem; recursive algorithm附录：详细程序清单#include<stdio.h>#define N 100int limitw, /*

15、限制的总重量*/totv, /*全部物品的总价*/maxv; /*可实现最大总价值*/int opionN, /*方案的选择*/copN; /*当前方案的选择*/struct /*背包问题结构体*/int weight; int value; aN;int n; /*物品种数*/void find(int i,int tw,int tv) int k;if(tw+ai.weight<=limitw) /*物品i包含在当前方案的可能性*/ copi=1;if(i<n-1)find(i+1,tw+ai.weight,tv);elsefor(k=0;k<n;k+)opionk=co

16、pk;maxv=tv;copi=0;if(tv-ai.value>maxv) /*物品i不包含在当前方案的可能性*/if(i<n-1)find(i+1,tw,tv-ai.value);elsefor(k=0;k<n;k+)opionk=copk;maxv=tv-ai.value;void main()int k,w,v;printf("物品种数：");scanf("%d",&n);for(totv=0,k=0;k<n;k+)printf(" 第%d种物品（重量，价值）：",k+1);scanf("%d,%d",&w,&v);ak.weight=w;ak.