| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1466 人关注过本帖
标题:[原创][背包问题贪婪法]
取消只看楼主 加入收藏
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
 问题点数:0 回复次数:0 
[原创][背包问题贪婪法]
题目大概意思:
比如说一堆食物。他们有重量。有热量。现在你可以任意选来吃。可以吃一个。可以吃半个。或者是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);
}
图片附件: 游客没有浏览图片的权限,请 登录注册

搜索更多相关主题的帖子: 背包 贪婪 
2005-06-12 11:01
快速回复:[原创][背包问题贪婪法]
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017873 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved