实验报告8 蛮力动态规划01背包.doc

《算法设计与分析》实验报告八
学号: 1004091130
姓名: 金玉琦
日期: 2011-12-5
得分:
一、实验内容:
分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。
二、所用算法的基本思想及复杂度分析:
蛮力法
基本思想
用蛮力法求解就是要穷举出物品的所有组合,计算不超过背包容量的物品的最大价值和
复杂度分析
装法有2n种组合,每种组合中又要计算价值和,所以其复杂度为指数级。
动态规划法
基本思想
动态规划法的关键在于找到决策函数,在本例中,令V(i,j)表示在前i个物品中能够装入容量为j的背包中的物品的最大值,则有如下动态规划函数:
V(i,0)=V(0,j)=0; (1)
V(i-1,j) j<wi
V(i,j)= (2)
max{V(i-1,j),V(i-1,j-wi)+vi} j>=wi
式(1)表明:把前面i个物品的装入容量为0的背包和把0个物品装入容量为j的背包,得到的总价值都是0。式(2)的第一个式子表明:如果第i个物品的重量大于背包的容量,则装入前i个物品得到的最大值和装入前i-1个物品得到的最大价值是相同的,即物品i不能装入背包;第二个式子表明:如果第i个物品的重量小于背包的容量,则会有以下两种情况:,则背包中的物品价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi;,则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然取二者的较大值作为把前i个物品装入容量为j的背包中的最优解。
复杂度分析
时间复杂度是O(n*c)。
回溯法
基本思想
回溯法是一种有组织的系统化搜索技术,可以看作是蛮力法穷举搜索的一种改进。具体在0/1背包问题中的使用如下:
回溯法从0/1背包问题的解空间树的根节点出发,按照深度优先遍历解空间树,搜索满足约束条件的解。在搜索到树中的任一结点时,先判断该结点的对应部分的解是否满足约束条件,或者是否超出目标函数的界,也就是判断该结点是否包含问题的(最优)解,如果不包含则跳过对以该结点为根的子树的搜索;否则进入以该结点为根的子树继续深度优先遍历搜索。
复杂度分析
0/1背包问题的解空间树是一棵子集树,遍历一棵子集树所需时间为Ω(2n)。
分支限界法
基本思想
分支限界法按照广度优先法遍历整个解空间树,在遍历过程中,对已经处理过的每一个结点根据限界函数估算目标函数的可能值,从中选取使目标函数取得极大或极小的结点优先进行广度优先搜索,从而不断调整搜索方向,尽快找到问题的最优解。
复杂度分析
由于分治限界法是蛮力法的一种改进,所以在0/1背包问题中,问题的复杂度在最坏的情况下是指数阶的。
三、源程序及注释:
#define MAX 100
#define max(a,b) (a>b)?a:b
#include <>
#include <VECTOR>
#include <>
#include <>
#include <>
#include <>
#include <IOSTREAM>
#include <algorith