0-1背包(动态规划、回溯)和背包(贪心)实验报告.doc

西安郵電學院
算法设计与分析课内试验报告
题目:0-1背包(动态规划、回溯)和背包(贪心)
院系名称: 计算机学院
专业名称: 软件工程专业
班级: 0903班
学生姓名: 张桥
学号(8位): 04095091(23)
指导教师: 陈琳
时间: 2011年12月
一. 设计目的
通过上机实验:
深刻理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。
二. 设计内容
1问题的描述
0-1背包问题
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大?
(2)背包问题与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1<=i<=n。
2算法设计思想
(1)0-1背包问题
动态规划法:是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
设所给0-1背包问题的子问题的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下。

回溯法:在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。
背包问题
贪心算法:首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。

正常测试数据(3组)及运行结果
0-1背包问题:
动态规划法:
回溯法:
背包问题:
贪心算法:
,设计技巧及体会
本次的实验大体理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。
通过本次上机实验,我对0-1背包(动态规划算法、回溯算法)和背包(贪心算法)有了更为深刻的了解,利用动态规划算法、回溯算法和贪心可以将问题简化,这有助于我们在实际问题中解决一些复杂性较大的问题,提高程序的运行效率。但要注意他们的区别与不同的应用场景。
五. 源代码
1)0-1背包:
动态规划法:
#include <>
#define MAX 20
void Knapsack(int *value, int *weight, int column, int length, int (*middle)[MAX]);
void TraceBack(int (*middle)[MAX], int *weight, int column, int length, int *x);
int Max(int x, int y);
int Min(int x, int y);
int Min(int x, int y)
{
return x <= y ? x : y;
}
int Max(int x, int y)
{
return x >= y ? x : y;
}
void TraceBack(int (*middle)[MAX], int *weight, int column, int length, int *x)
{
int i;
for(i = 1; i < length; i++)
if(middle[i][column] == middle[i + 1][column])
x[i] = 0;
else
{
x[i] = 1;
column -= weight[i];
}
x[length] = (middle[length][column] ? 1 : 0);
}
void Knapsack(int *value, int *weight, in