数据结构课程设计背包问题的求解_数据结构课程设计心得

2020-02-27 其他范文下载本文

数据结构课程设计背包问题的求解由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计心得”。

2009届电子信息科学与技术专业数据结构课程设计

背包问题的求解

摘要组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。关键词背包问题；

递归算法；

1问题描述

1.1问题描述

背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

1.2基本思想

（1）分别输入n件物品的重量和价值。（2）采用递归寻找物品的方案。

（3）输出最佳的装填方案，包括选中的是哪几种物品，总价值为多少。

2问题分析

背包问题的求解是一个很经典的案例。对于它的分析与研究已经到达了一定的深度，解决这个问题有很多很多的办法。其中递归方法是比较简化程序，也比较难理解的一个。

设n件物品的重量分别为w0,w1,„,wn-1,物品的价值分别为v0,v1,„,vn-1。采用递归寻找物品的选择方案。设前面已经有了多种选择方案，并保留了其中最大的选择方案于数组option[],设方案的的总价值存于变量maxv,当前正在考察新方案其物品选择情况保存于数组cop[]，嘉定当前方案已经考虑了前i-1件物品，现在正在考虑第i件物品；当前方案已经包含的物品的质量之和为tw;至此，若其余物品都选择可能的话，本方案能达到的总价值的期望值设为tv，算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，急需考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会不会再被考察。这同时保证函数后找到的方案一定会比前面的方案更好。2009届电子信息科学与技术专业数据结构课程设计对于第i件物品的选择有两种可能：

（1）物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后，继续递归去考虑其余物品的选择；

（2）物品i不被选择，这种可能性仅当不包物品i也有可能会找大价值更大的方案的情况。

就此，通过不断地对从第一件开始的物品到第n件物品进行选择或是不选择，从而从各个方案的比较中选择出最优方案。

采用option[]和cop[]两个数组，来辅助完成递归寻找物品的选择方案。数组option[]起到一个“旗帜”作用，用来区别于未被选择的物品，从而达到输出被选择的函数。而cop[]则像是一个中间变量，它在递归过程中不断地发生变化，将有效的最终数据传输给数组option[]，起到一个桥梁作用。

3数据结构描述

背包问题结构体：

struct{

int weight;

int value;

}a[N];4算法设计

4.1程序流程图

2009届电子信息科学与技术专业数据结构课程设计

图4-1 程序流程图

4.2算法设计

根据问题分析中的思想写出递归算法如下：

find（物品当前选择已达到的重量和tw,本方案可能达到的总价值为tv）｛

/*考虑物品i包含在当前方案中的可能性*/ if（包含物品i是可接受的）｛

将物品i包含在当前方案中；

if(i

以当前方案作为临时最佳方案保存；

恢复物品i不包含状态；

｝ 2009届电子信息科学与技术专业数据结构课程设计

/*考虑物品i不包含在当前方案中的可能性*/ if（不包含物品i仅是可考虑的）

if(i

以当前方案作为临时最佳方案保存；

｝

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight

/*物品i包含在当前方案的可能性*/ { cop[i]=1;if(imaxv)

/*物品i不包含在当前方案的可能性*/ if(i

2009届电子信息科学与技术专业数据结构课程设计

opion[k]=cop[k];maxv=tv-a[i].value;} } 5详细程序清单

详细程序清单见附录。

6程序运行结果

背包问题求解界面如图6-1所示。

图6-1 背包问题求解界面

程序调试成功。

在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号像“；”也很容易丢掉或是中英文格式不正确；甚至像0和 O这种小错误有时也会发生，在经过调试和完善程序的过程中，这些错误已经全部改正。在此过程中我们学到了不少调试的技巧，极大得丰富了编程的知识，这些在程序的优化方面帮助很大。

7心得体会

通过此次课程设计的实践，感触较深。不仅使我们加深了对书本知识的理解，而且锻炼了我们编写程序、调试程序的能力。同时，此次课程设计也充分弥补了课堂教学中知识的缺陷。这次课程设计由于时间有限，对有些地方考虑的还不够周到。

2009届电子信息科学与技术专业数据结构课程设计

在本课题中，我们研究了如何用递归算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。所以我们试着用所学的数据结构知识以及递归法来解决普通的背包问题。背包问题的递归思想确实有点难以理解，为了理解这个思想，我们确实花了很长时间，不过很高兴最后经过我们的讨论掌握了这个思想。

参考文献

[1] 徐孝凯.数据结构课程实验.北京：清华大学出版社，2002:100-132 [2] 张乃笑.数据结构与算法.北京：电子工业出版，2000:3-5 [3] 严蔚敏.数据结构（C语言版）.北京：清华大学出版社，2002:100-132 [4] 李春葆.数据结构（C语言篇）习题与解析（修订版）.北京：清华大学出版，2000:45-66

Knapsack problem solving

Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009届电子信息科学与技术专业数据结构课程设计

附录：详细程序清单

#include #define N 100 int limitw,/*限制的总重量*/ totv, /*全部物品的总价*/ maxv;

/*可实现最大总价值*/ int opion[N],cop[N];

struct{

int weight;

int value;

}a[N];int n;

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight

{ cop[i]=1;if(i

/*方案的选择*/ /*当前方案的选择*/ /*背包问题结构体*/

/*物品种数*/ /*物品i包含在当前方案的可能性*/ 7