怎么论坛突然间多了这个。而且版主还是神vlinux飘飘。看来神的动作还是最快的。希望以后这里经常有高手。。。。让偶学多点东西~~~~~~~

背包问题：
有不同价值，不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的重量不超过指定的限制重量，但选中的物品价值最打。
#include<stdio.h>
#include<math.h>
void comb(int s[],int i)/*求每一次取的物品.s[]是做标记的*/
{   int j=0;
while(i>0)
    { s[j++]=i%2;
      i=i/2;
    }
}
main()
{  int v[]={10,12,13,15,7,9};/*v为物品价钱*/
   int w[]={15,8,12,10,5,6};/*w为物品重量*/
   int sign[10],tw,maxv=0,i,j,k,temp_w,temp_v;/*sign[]存放每一次的方案
             tw是你输入的重量.temp_w是累加重量的
             temp_v是累加价值的*/
   int biao[10];/*存放最大值时候的标记*/
   printf("请输入背包的最大容量:\n");
   scanf("%d",&tw);
   for(i=0;i<pow(2,6);i++) /*一共有pow(2,n)种,比如你有2个物品的时候.
         就有00 01 10 11 4种情况.1就是表示取的物品*/
   { comb(sign,i);
      temp_w=0;
   temp_v=0;
      for(j=0;j<10;j++)
        if(sign[j]==1)    /*你所取的方案.1的就是表示取*/
  {  temp_w=temp_w+w[j];
        temp_v=temp_v+v[j];
  }
  if(temp_w<=tw&&temp_v>maxv)/*当这种方案的总重量不大于你限制的重量.
           和大于每一次求出来的最大值*/
  {  
   maxv=temp_v;
   for(k=0;k<10;k++)
    biao[k]=sign[k];  /*将最大值方案用数组biao[]来存放*/
  }
   }
    printf("你取的方案是:\n");/*以下为输出*/
   for(k=0;k<10;k++)
   {   
    if(biao[k]==1)
     printf("%d\t",w[k]);
   }
     printf("\n");
   for(k=0;k<10;k++)
   {
   if(biao[k]==1)
    printf("%d\t",v[k]);
   }
   printf("背包取的最大值是:%d\n",maxv);
}
对这个算法有兴趣而有看的不太明白的就加我QQ吧。
QQ：59071323
POPO：luodongming
E-mail: ldm03@

[此贴子已经被作者于2005-8-12 18:55:03编辑过]

题目大概意思： 比如说一堆食物。他们有重量。有热量。现在你可以任意选来吃。可以吃一个。可以吃半个。或者是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=(v/w); 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)/*全装情况*/ { tw=tw-w; max=max+v; biao[k++]=1; i++; } else if(tw>0&&tw<=w)/*只能装1/n的情况*/ { max=max+((tw/w)*v); biao[k++]=tw/w; 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-6-16 8:18:22编辑过]

举报：楼主重复发帖哦……（纯属灌水）

牛虻。你好笨呀。你怎么不看看我写的标题是什么。摆明就是灌水嘛

[此贴子已经被作者于2005-6-16 8:37:27编辑过]

关于算法的问题我是怎么看怎么迷糊！

第一帖怎么就灌水了

     晕。静大哥你看看我算法嘛。也不完全算是灌水拉

还不错..