C++程序设计例解(05)

05. 从n个不同价值、不同重量的物品中选取一部分，在不超过限定的总重量的前提下，使该部分的价值最大。这里假定的总重量不超过n个物品的总重量总和，且没有一样物品的重量超过限定的总重量。
解：
这个问题是求最佳解的典型例子。为找最佳解，需生成所有可能的解。在生成这些解的同时，保留一个指定意义下的当前最佳解，当发现一个更好的解时，就把这个解改为当前最佳解，并保留之。
现给出一组n个物品中找出满足约束条件的最佳解的通例。为便于构造算法，采用递归方法。构成可接受解的所有选择是通过依次考察组中的各个物品的结果，对每个物品的考察均有两种可能：或所考察的物品被包括在当前选择中，或所考察的物品不被包括在当前选择中。递归函数是描述指定物品被包括或不被包括在当前选择中的计算过程，只要指定物品被包括后重量满足约束条件，该物品被包括是应该被考虑的；仅当一个物品如不被包括也可能达到比当前最佳解所达到的总价值大时，为满足重量的限制，不把该物品包含在当前选择中也是应该被考虑的。为此，递归函数设有三个参数：指定的物品、当前选择已达到的总重量和可能达到的总价值。下面的递归算法就是考察某个物品在当前选择中是否被包括的计算过程描述。
算法—物品i在当前选择中被包括与否的递归算法
try(物品i，当前选择已达到的总重量tw，可能达到的总价值tv)
{
/*考察当前选择包含物品i的合理性*/
if(包含物品i是可接受的)
{
将物品i包括在当前解中；
if(i<n-1(try(i+1,tw+物品i的重量，tv);
else
调整当前最佳解；
将物品i从当前解中消去；
}
/*考察当前选择不包含物品i的合理性*/
if(i<n-1)try(i+1,tw,tv-物品i的价值)；
else
调整当前最佳解；
}
对当前选择而言，“包含物品i是可接受的”准则是它被包括后，有可能达到的总价值也不小于当前最佳解所达到的价值，因为如果小于的话，继续考察下去也不会产生更好的解。

程序代码如下：
#include<stdio.h>
#define N 100
double limw, /*物品的约束重量*/
totv, /*全部物品的总价值*/
maxv; /*解的总价值*/
int opts[N], /*当前最佳选择*/
cs[N]; /*当前选择*/
int n, /*物品数*/
k; /*工作变量*/
struct{
double weight; /*物品的重量*/
double value; /*物品价值*/
}a[N]; /*一组物品*/
void tryy(int i,double tw,double tv)
{
/*考察当前选择物品i的合理性*/
if(tw+a[i].weight<=limw) /*包含物品i是可接受的*/
{
cs[i]=1; /*将物品i包括在当前解中*/
if(i<n-1)tryy(i+1,tw+a[i].weight,tv);
else
if(tv>maxv)
{ /*调整当前最佳解*/
for(k=0;k<=i;k++)
opts[k]=cs[k];
maxv=tv;
}
cs[i]=0; /*将物品i从当前解中消去*/
}
/*考察当前选择不包含物品i的合理性*/
if(tv-a[i].value>maxv) /*不包含物品i是可接受的*/
if(i<n-1)
tryy(i+1,tw,tv-a[i].value);
else
{ /*调整当前最佳解*/
for(k=0;k<=i;k++)
opts[k]=cs[k];
maxv=tv-a[i].value;
}
}
void main()
{
printf(“Enter number of mails.\n”);
scanf(“%d”,&n);
printf(“Enter limit of weight.\n”);
scanf(“%lf”,&limw);
printf(“Enter weight and value of mails.\n”);
for(k=0;k<n;k++)
scanf(“%lf%lf”,&a[k].weight,&a[k].value);
for(totv=0.0,k=0;k<n;k++)
totv+=a[k].value;
maxv=0;
for(k=0;k<n;k++)
opts[k]=cs[k]=0;
tryy(0,0,totv);
for(k=0;k<n;k++)
if(opts[k])
printf(“%4d”,k+1);
printf(“\nTotal value = %lf\n”,maxv);
}