实验项目三 用蛮力法、动态规划法和贪心法求解背包问题

实验项目三 用蛮力法、动态规划法和贪心法求解0/1

背包问题

实验目的

1、学会背包的数据结构的设计，针对不同的问题涉及到的对象的数据结构的设计也不同；

2、对0-1背包问题的算法设计策略对比与分析。

实验内容：

0/1背包问题是给定n个重量为{w1, w2, … ,wn}、价值为{v1, v2, … ,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。

在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：

n wixi C i 1 xi {0,1}(1 i n)（式1）

（式2）

max vixii 1n

于是，问题归结为寻找一个满足约束条件式1，并使目标函数式2达到最大的解向量X=(x1, x2, …, xn)。

背包的数据结构的设计：

typedef struct object

{

int n;//物品的编号

int w;//物品的重量

int v;//物品的价值

}wup;

wup wp[N];//物品的数组，N为物品的个数

int c;//背包的总重量

1、蛮力法

蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。

用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。

所以蛮力法解0/1背包问题的关键是如何求n个物品集合的所有子集，n个物品的子集有2的n次方个，用一个2的n次方行n列的数组保存生成的子集，以下是生成子集的算法：

void force(int a[16][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]);

}

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;

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++)

{

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。

这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：

V(i, 0)= V(0, j)=0 （式3）

j w V(i 1,j) V ( i , j ) i (式4) V(i 1,j),V(i 1,j wi) vi}j wi max{

式3表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式4的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：

（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容 …… 此处隐藏：2950字，全部文档内容请下载后查看。喜欢就下载吧 ……