Question

关于一道C语言的背包问题，用的是贪心算法

题目是：利用贪心策略解决背包问题。现有载重为M公斤的背包和n种货物。第i种货物的重量为Wi，它的总价值为Pi，假定M、Wi、Pi均为整数。设计程序给出装货方法，使装入背包的货物总价值达到最大。

我这边用的例子是：包的最大负重=20 所有种类的物品数=3种
第一种物品重量=15，价值=18
第二种物品重量=10，价值=15
第三种物品重量=8，价值=10

最终的结果输出是：物品二 10公斤 物品三 8公斤 物品一 2公斤
总价值达到最大=27.4

我不知道自己的程序哪里出了问题。看上去好像都对啊。。。

请指导一下，谢谢！！
因为程序字比较多，所以这边写不上 我穿个马甲过来，把自己的程序给大家看看~
回答的第一条就是我的程序，请帮帮忙·

我这边是在DEV-C 下运行的

Answer 1

#include "iostream.h"
#include "stdio.h"
#include <cstdlib>

struct stone
{
int name;
int weight;//物品的剩余重量
int weight_t;//物品的重量
float benefit;//物品的价值
//float b;
};

//按物品的效益排序
void sort(stone *data,int num)
{
//仅剩一个元素时排序完毕
if(num<1)
return;

int low=0,high=num;
stone key_s=data[low];//取数组的第一个作为关键字
float key=(float)key_s.benefit/key_s.weight;
int empty=low;//目标位置初始位置为low指向的位置

while(low<high)
{
if(low==empty)//后面的指针向前走
{
//找到比关键字小的元素把它移到low指向的位置
while((data[high].benefit/data[high].weight<key)&&(high>low))
{
high--;
}
if(data[high].benefit/data[high].weight>=key)
{
data[low]=data[high];
empty=high;
}
}
else if(high==empty)//前面的指针向后走
{
//找到比关键字大的元素把它移到high指向的位置
while((data[low].benefit/data[low].weight>=key)&&(low<high))
{
low++;
}
if(data[low].benefit/data[low].weight<key)
{
data[high]=data[low];
empty=low;
}
}
}

data[empty]=key_s;//把关键字放到划分完毕后两部分的中间位置

//关键字前面的数列继续递推
if(empty>1)
sort(data,empty-1);

//关键字后面的数列继续递推
if(num-empty-1>0)
sort(data+empty+1,num-empty-1);
}

//输入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("请输入第%d号物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必须大于0!\n");}
printf("请输入第%d号物品的价值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的价值必须大于0!\n");}
bag[i].weight_t=bag[i].weight;
}
}

//主函数
int main(int argc, char* argv[])
{ int i;
int num=0;//放入物品的数量
int weight=0;//背包可容纳的重量
float benefit=0;//总效益
stone *bag;//物品

/////输入背包可容纳的重量
do
{
printf("请输入背包可容纳的重量:");
scanf("%d",&weight);
if (weight<=0)
printf("背包可容纳的重量必须大于0!\n");
}while(weight<=0);

//输入物品种类
do
{
printf("请输入物品的数量:");
scanf("%d",&num);
if (num<=0)
printf("物品数量必须大于0!\n");
}while(num<=0);

bag=new stone[num];//物品数组

inputstone(bag,num);//输入物品的信息
sort(bag,num-1);//按单位效益排序

for(i=0;i<num&&weight>0;i++)
{
stone *temp=bag+i;

if(weight>=temp->weight)
{
weight-=temp->weight;
temp->weight=0;
benefit+=temp->benefit;
continue;
}
else
{
temp->weight-=weight;
weight=0;
benefit+=(temp->benefit*(1-(float)temp->weight/temp->weight_t));
break;
}
}

////////输出结果//////////
printf("物品种类 放入的比例 每单位效益 ");
for(i=0;i<num;i++)
{
stone *temp=bag+i;

printf("%d类物品",temp->name);
printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(float)temp->weight_t);
printf(" %.4f\n",temp->benefit/(float)temp->weight_t);
}
printf("总效益:%.2f",benefit);
delete bag;
getchar();
system("PAUSE");
return EXIT_SUCCESS;
return 0;
}

Answer 2

//输入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("请输入第%d号物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必须大于0!\n");}
printf("请输入第%d号物品的价值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的价值必须大于0!\n");}
bag[i].weight_t=bag[i].weight;
}
}

这部分中的
scanf("%f",&bag[i].benefit); //缺少&
把这行加上&就对了

Answer 3

shayisi?