问题描述;

有不同价值,不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,是选中的物品总重量不超过指定的限制重量,但是选中的物品的价值之和最大.

[分析]

这个经典的问题的较高效率的方法是一般是递归和贪婪法,但是我在软件考试参考书上看到这个题目用了一个很好的算法(搜索法),是把每一种解决的可能情况转换成2进制的数来表示,我第一次看到这个方法真的很好(也许是我太菜了的原因吧,呵呵~~~~~~~~~)

大家来一起讨论一下:

程序代码:

#include
#include
using namespace std;
const int MAX=100;
int change_base(float b[],int num)
{
 int tempt=num/2,i=0,yushu;
 yushu=num%2;
 while(tempt!=0)
 {
      b[i]=yushu;
   num=tempt;
   tempt=num/2;
   yushu=num%2;
   i++;
 }
 b[i]=1;
  return i;
}

int main()
{
 int num;
 cout< cin>>num;
 float wMax;
 cout< cin>>wMax;
 cout< float w[MAX],v[MAX],b[MAX];
 int tempt[MAX];
 for(int i=0;i  cin>>w[i]>>v[i];
 int m=0,n=0,s;
 float weigh,value,Maxvalue;
 for(int j=0;j {
        for(int k=0;k   b[k]=0;
  m=change_base(b,j);
  weigh=0.0;
  value=0.0;
       for(n=m;n>=0;n--)
     if(b[n]==1)
     {
             weigh+=w[n];
    value+=v[n];
     }
     if((weighMaxvalue))
     {
      Maxvalue=value;
      for(s=0;s<=m;s++)
       tempt[s]=b[s];
     }
 }
 cout< cout< cout<<"此时,物品所装物品的价值依次是:"< for(int p=0;p<=s-1;p++)
 if(tempt[p]==1)
 cout<

评论