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

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

[cpp]
#include
#define M 5

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;
}
}
}
}

//装载主要方法
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;
}else{
Node[i].flag=0;
}
}
}

//进行结果的输出
void putout(){
int i;
printf("选中物品的重量分别为：");
for(i=0;i if(Node[i].flag){
printf("%.2f ",Node[i].weight);
}
}
printf("\n总价值为:%.2f",curvalue);
}


int main(){
int i;
printf("请输入物品的重量和价值：\n");
for(i=0;i printf("请输入第%d个物品的重量和价值",i+1);
scanf("%f%f",&Node[i].weight,&Node[i].value);
}
printf("\n请输入背包容积：");
scanf("%f",&Weight);
sort();
load();
putout();
return 0;
}

#include
#define M 5

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;
}
}
}
}

//装载主要方法
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;
}else{
Node[i].flag=0;
}
}
}

//进行结果的输出
void putout(){
int i;
printf("选中物品的重量分别为：");
for(i=0;i if(Node[i].flag){
printf("%.2f ",Node[i].weight);
}
}
printf("\n总价值为:%.2f",curvalue);
}

int main(){
int i;
printf("请输入物品的重量和价值：\n");
for(i=0;i printf("请输入第%d个物品的重量和价值",i+1);
scanf("%f%f",&Node[i].weight,&Node[i].value);
}
printf("\n请输入背包容积：");
scanf("%f",&Weight);
sort();
load();
putout();
return 0;
}