当前位置:文档之家› 背包问题(贪心算法)

背包问题(贪心算法)

算法分析与设计实验报告
第 4 次实验
}
附录:完整代码
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct node{
float value;
float weight;
};
float Value,curvalue=0;
float Weight,curweight=0;
//按价重比冒泡排序
void sort(node Node[],int M){
int i,j;
node temp;
for(i=0;i<M-1;i++){
for(j=i+1;j<M;j++){
if((Node[i].value/(float)Node[i].weight)<Node[j].value/(float)Node[j].weight){ temp=Node[i];
Node[i]=Node[j];
Node[j]=temp;
}
}
}
printf("物品的价重比从高到低依次排列为:\n");
for(i=0;i<M;i++){
printf("%.2f ",Node[i].value);
}
printf("\n");
for(i=0;i<M;i++){
printf("%.2f ",Node[i].weight);
}
}
//装包主要方法及输出
void pack(node Node[],int M){
int i,j=1;
printf("\n\n选中物品的价格为:\n");
for(i=0;i<M;i++){
if((Node[i].weight+curweight)<=Weight){
curvalue+=Node[i].value;
curweight+=Node[i].weight;
printf("第j次选择为:%.2f \n",curvalue); j++;
}
}
}
int main(){
int i,M;
printf("\n请输入背包容积:");
scanf("%f",&Weight);
printf("\n请输入物品个数:");
scanf("%d",&M);
node Node[M];
srand(time==NULL);
for(i=0;i<M;i++){
Node[i].weight=rand()%10;
Node[i].value=rand()%10;
}
sort(Node,M);
pack(Node,M);
return 0;
}。

相关主题