蛮力法,动态规划法,贪心法求解背包问题
- 格式：doc
- 大小：202.00 KB
- 文档页数：28
算法设计与分析
实验名称：用蛮力法、动态规划法和贪心法求
0/1背包问题
作者姓名 ： xxx
xxx
xxx
完成日期：2013年9月22日星期日
组的编号：28
目录
第一章：简介 ............................................................................................ 1
第二章：算法规范 .................................................................................... 2
数据结构.................................................................................................. 2
伪代码 ................................................................................................... 3
第三章：算法测试 .................................................................................... 4
蛮力法 ................................................................................................ 4
动态规划............................................................................................... 5
贪心法 ................................................................................................... 5
第四章：分析讨论 .................................................................................... 6
算法分析.................................................................................................. 6
时间复杂度分析 ................................................................................ 16
附录 ........................................................................................................... 17
声明 ........................................................................................................... 17
第 1 页 第一章：简介
问题的描述：
0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1,
v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。
在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：
于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1, x2, …, xn)。
背包的数据结构的设计：
typedef struct object
{
int n;//物品的编号
int w;//物品的重量 niiixv1max（式2） )1(}1,0{1nixCxwiniii（式1）
第 2 页 int v;//物品的价值
}wup;
wup wp[N];//物品的数组，N为物品的个数
int c;//背包的总重量
第二章:算法规范
数据结构：
0/1背包问题是给定n个重量为{w1, w2, „ ,wn}、价值为{v1,
v2, „ ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中，在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的 第 3 页 情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。
所以，我们用了数组，函数作为主要的数据结构。用蛮力法、动态规划法和贪心法求解0-1背包问题的算法设计对比与分析。
伪代码如下所示
一、蛮力法
1,
1.1，定义物品结构
1.2 input 物品编号，重量，价值
2，蛮力法产生子集
3，判断子集的可行性
4从可行解中找出最优解
5输出最优解
二、动态规划法
1.1 定义物品结构wup
1.2定义物品输入函数inputwp
1.3定义物品输出函数outputwp
2，定义函数findmaxvalue
3，输入物品
4，调用findmaxvalue 第 4 页 5，输出结果
三、贪心法
1.1 定义物品结构wup
1.2 输入物品
2，对v/w排序
3，输出物品
4，选择物品
5，计算物品总价值
6，输出物品总价值和最优解
第三章：测试结果
1.蛮力法 第 5 页
2.动态规划法
第 6 页 3.贪心法
这个结果没有运行出来，请老师原谅，谢谢。
第四章：分析和讨论
（一）算法思想分析：
1．蛮力法：
蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。
用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。
所以蛮力法解0/1背包问题的关键是如何求n个物品集合的所有 第 7 页 子集，n个物品的子集有2的n次方个，用一个2的n次方行n列的数组保存生成的子集，以下是生成子集的算法：
void force(int a[][4])//蛮力法产生4个物品的子集
{
int i,j;
int n=16;
int m,t;
for(i=0;i<16;i++)
{ t=i;
for(j=3;j>=0;j--)
{
m=t%2;
a[i][j]=m;
t=t/2;
}
}
for(i=0;i<16;i++)//输出保存子集的二维数组
{
for(j=0;j<4;j++)
{
printf("%d ",a[i][j]); 第 8 页 }
printf("\n");
}
｝
以下要依次判断每个子集的可行性，找出可行解:
void panduan(int a[][4],int cw[])////判断每个子集的可行性，如果可行则计算其价值存入数组cw,不可行则存入0
{
int i,j;
int n=16;
int sw,sv;
for(i=0;i<16;i++)
{
sw=0;
sv=0;
for(j=0;j<4;j++)
{
sw=sw+wp[j].w*a[i][j];
sv=sv+wp[j].v*a[i][j];
}
if(sw<=c)
cw[i]=sv; 第 9 页 else
cw[i]=0;
}
在可行解中找出最优解，即找出可行解中满足目标函数的最优解。以下是找出最优解的算法：
int findmax(int x[16][4],int cv[])//可行解保存在数组cv中，最优解就是x数组中某行的元素值相加得到的最大值
{
int max;
int i,j;
max=0;
for(i=0;i<16;i++)
{
if(cv[i]>max)
{max=cv[i];
j=i;
}
}
printf("\n最好的组合方案是：");
for(i=0;i<4;i++)
{ 第 10 页 printf("%d ",x[j][i]);
}
return max;
}
2．动态规划法：
动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。
动态规划法设计算法一般分成三个阶段：
（1）分段：将原问题分解为若干个相互重叠的子问题；
（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；
（3）求解：利用递推式自底向上计算，实现动态规划过程。
0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, …,
xi-1)，在决策xi时，问题处于下列两种状态之一：
（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；
（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。
