数据结构背包问题的求解

更新时间：2024-05-17 17:40:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

德州学院物理系 2009届电子信息科学与技术专业数据结构课程设计

背包问题的求解

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

下，追求总的最大收益的资源有效分配问题。

关键词背包问题；递归算法

1问题描述

1.1问题描述

背包问题是一种组合优化的NP完全问题。问题可以描述为：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。它主要分为以下几种问题：

（1）0/1背包问题

有n件物品和一个容量为v的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 (2)完全背包问题

有n种物品和一个容量为v的背包，每种物品都有无限件可用。第i种物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个问题非常类似于0/1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。

（3）多重背包问题

有n种物品和一个容量为v的背包。第i种物品最多有n件可用，每件体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

德州学院物理系 2009届电子信息科学与技术专业数据结构课程设计

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n+1种策略：取0件，取1件……取 n件。

各类复杂的背包问题总可以变换为简单的0/1背包问题。本次课程设计主要研究0/1背包问题的求解。

1.2基本思想

0/1背包问题的求解是一个很经典的案例。对于它的分析与研究已经到达了

一定的深度，解决这个问题有很多很多的办法。其中比较常用的有以下几种方法：（1）回溯法

回溯法的主要思想：首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出放弃，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，因此要用到栈。

（2)贪心法

根据贪心的策略，每次挑选价值最大的物品装入背包，判断得到的结果是否最优；每次挑选所占重量最小的物品装入，判断是否能得到最优解；每次选取单位重量价值最大的物品，判断是否能得到最优解。

（3）递归法

此法是穷举法的改进，利用递归函数依次选择每个物品，直到求出最优解。

分析比较以上各种方法，回溯法利用栈，程序较复杂；贪心法的最终结果不一定是最优解；递归方法是比较简化程序的一个方法，且比较容易理解。故本次课程设计选择利用递归法求解0/1背包问题。

递归法的基本思路为：

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

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

2问题分析

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

对于第i件物品的选择有两种可能：

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

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

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

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

3数据结构描述

背包问题结构体：

struct{

int weight; /*物品的重量*/ int value; /*物品的价值*/ }a[N];

4算法设计

德州学院物理系 2009届电子信息科学与技术专业数据结构课程设计

4.1程序流程图