【数据结构背包问题】数据结构背包问题的求解

篇一 : 数据结构背包问题的求解

德州学院 物理系 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。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

1

数据结构背包问题 数据结构背包问题的求解

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

这题目和完全背包问题很类似。［］基本的方程只需将完全背包问题的方程略

微一改即可，因为对于第i种物品有n+1种策略：取0件，取1件……取 n件。

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

研究0/1背包问题的求解。

1.2基本思想

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

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

（1）回溯法

回溯法的主要思想：首先将物品排成一列，然后顺序选取物品装入背包，假

设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该

件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如

果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物

品不合适，应将它取出放弃，继续再从它之后的物品中选取，如此重复，直至求

得满足条件的解，或者无解。由于回溯求解的规则是“后进先出”，因此要用到

栈。

（2)贪心法

根据贪心的策略，每次挑选价值最大的物品装入背包，判断得到的结果是

否最优；每次挑选所占重量最小的物品装入，判断是否能得到最优解；每次选取

单位重量价值最大的物品，判断是否能得到最优解。

（3）递归法

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

分析比较以上各种方法，回溯法利用栈，程序较复杂；贪心法的最终结果不

一定是最优解；递归方法是比较简化程序的一个方法，且比较容易理解。故本次

课程设计选择利用递归法求解0/1背包问题。

递归法的基本思路为：