[原创][背包问题贪婪法]
题目大概意思：比如说一堆食物。他们有重量。有热量。现在你可以任意选来吃。可以吃一个。可以吃半个。或者是1/3 。但是如何吃能得到物品的最大热量呢。以下程序就是解决这个问题的。
思想大概这样：热量大的未必能得到最大。因为你肚子有限吧。假如食物重量1公斤。放出的是5000。现在有一个0.3公斤。放出3000热量。在热量上来说是1公斤的事物多。但是他也重。这个时候要想得最大热量。就要求出每种食物的热量与重量之比。比值越大。代表效率越高。然后按照将序排列。得到食物热量与重量比值大的。小弟表达能力差。只能这样简单的说一下了。
#include<stdio.h>
main()
{
float v[]={25,24,15};/*物品价值*/
float w[]={18,15,10};/*物品重量*/
float Ratio[100],temp,temp_v,temp_w,tw,max=0.0;/*Ratio[]是求价值与重量的比值
temp_v累加物品价值
temp_w累加物品重量
max是求得的物品最大价值
tw表示背包的所能承受的最大重量*/
int i,j,k;
float biao[10];/*这个物品所取的重量之比,1表示全取.0.5表示取二分之一*/
for(k=0;k<10;k++)
biao[k]=0;
printf("请输入背包的最大容量:tw\n");
scanf("%f",&tw);
for(i=0;i<3;i++)
Ratio[i]=(v[i]/w[i]);
for(i=0;i<2;i++)/*按照比值将物品价值和重量降序排列*/
{
temp=Ratio[i+1];
temp_v=v[i+1];
temp_w=w[i+1];
j=i;
while(j>-1&&temp>Ratio[j])
{
Ratio[j+1]=Ratio[j];
v[j+1]=v[j];
w[j+1]=w[j];
j--;
}
Ratio[j+1]=temp;
v[j+1]=temp_v;
w[j+1]=temp_w;
}
i=0;
k=0;
while(tw>0)/*开始取物品.如果能装的一个就全装*/
{
if(tw>w[i])/*全装情况*/
{
tw=tw-w[i];
max=max+v[i];
biao[k++]=1;
i++;
}
else if(tw>0&&tw<=w[i])/*只能装1/n的情况*/
{
max=max+((tw/w[i])*v[i]);
biao[k++]=tw/w[i];
tw=0;
i++;
}
}
for(k=0;k<10;k++)/*以下是输出*/
if(biao[k]!=0)
printf("%f\t",biao[k]);
printf("\n");
printf("物品的重量是:\n");
for(k=0;k<10;k++)
if(biao[k]!=0)
printf("%f\t",w[k]);
printf("\n");
printf("所取的物品重量是:\n");
for(k=0;k<10;k++)
if(biao[k]!=0)
printf("%f\t",biao[k]*w[k]);
printf("\n");
printf("背包所取的重量是:%f\n",max);
}
