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

05.从N个不同值和权重的项目中选择一个部分，在不超过限定总权重的前提下，使该部分的值。这里假设的总重量不超过N件物品的总重量之和，没有一件物品的重量超过限定的总重量。
解决方案:
这个问题就是解决方案的典型例子。为了找到解决方案，需要生成所有可能的解决方案。在生成这些解决方案时，保持指定意义上的当前解决方案。当找到更好的解决方案时，将此解决方案更改为当前解决方案并保留它。
现在给出在一组N个项目中寻找满足约束条件的解的一般例子。为了便于构造算法，采用了递归方法。构成可接受的解决方案的所有选择都是依次检查组中每个项目的结果。检查每个项目有两种可能:要么被检查的项目包含在当前选项中，要么被检查的项目不包含在当前选项中。递归函数是一个计算过程，它描述指定的项是否包含在当前选择中。只要指定项的权重在被包含后满足约束条件，就应该考虑该项的包含；当只有一个项目，如果不包括，可能达到超过当前解决方案的总价值时，为了满足重量限制，也应考虑不将该项目包括在当前选择中。因此，递归函数有三个参数:指定的项目、当前选择达到的总权重和可能的总值。以下递归算法描述了检查项目是否包含在当前选择中的计算过程。
算法——当前选择是否包含第I项的递归算法
try(第I项，当前选择达到的总权重tw，可能的总值tv)
{
/*考察当前选择包含第I项的合理性*/[br/] if(包含第I项
if(ielse
调整当前解；
从当前解决方案中删除项目I；
}
/*考察当前选择中不包含第I项的合理性*/
if(ielse
调整当前解决方案；
}
对于当前的选择，“包含第I项是可以接受的”的标准是，包含后，可能的总价值不小于当前解的总价值，因为如果是，进一步考察也不会产生更好的解。