贪心算法解决0-1背包问题

贪心算法--0-1背包问题

贪心算法--0-1背包问题

1、问题的描述

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,4,2,1,3，它们的价值分别是3,5,6,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

贪心算法的思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。

2、代码及注释

#include #define M 5

//定义一个node结构体，用来存放物体的重量和价值 struct node {

float value;//价值 float weight;//重量

int flag; //用来判别这个物体是否装进背包 }Node[M],temp;

float Value,curvalue=0;//总价值和当前价值

float Weight,curweight=0;//背包的最大承受重量和现有重量

//按性价比排序 void sort() {

int i,j;

//遍历所有物品 {

//与之后的物品进行比较 {

//判断性价比较最高性价比

for(i=0;i

for(j=i+1;j

if((Node[i].value/(float)Node[i].weight)

{

//进行交换

temp=Node[i]; Node[i]=Node[j]; Node[j]=temp;

1

贪心算法--0-1背包问题

}

//装载主要方法 void load() {

int i;

//遍历所有物品 {

//判断加入物品否是否大于背包所能承载的最大重量

for(i=0;i

}

}

}

if((Node[i].weight+curweight)<=Weight)

{

curvalue+=Node[i].value; curweight+=Node[i].weight; Node[i].flag=1;//进行标记 }

//进行结果的输出 void putout() { int i;

printf(\选中物品的重量分别为：\ for(i=0;i

if(Node[i].flag)

{ }

printf(\ }

printf(\总价值为:%.2f\}

int main()

} else {

//进行标记

Node[i].flag=0;

} }

2

贪心算法--0-1背包问题

{

int i;

printf(\请输入物品的重量和价值：\\n\ for(i=0;i

{

printf(\请输入第%d个物品的重量和价值\ scanf(\

}

printf(\请输入背包容积：\ scanf(\ sort(); load(); putout(); return 0; }

3、运行结果

(1)在某种情况下可以通过局部最优选择达到整体最优。

(2)贪心算法并不能使所有符合局部最优的选择使得整体达到最优

4、运行结果

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

在这个程序中，采用性价比的方式来做出当前最好的选择，然后再不大于背包所能承载的最大重量的时候将他标记成1，否则标记成0.

最后在输出的时候选择标记为1 的输出，用来实现贪心算法。

3