dynamic-programming - 为什么该算法用于整数 Knapsack 不正确?

  显示原文与译文双语对照的内容

这就是我想做的。

给定'n'项的权重'wi'和值'vi',我需要最大化 Knapsack的值,保持在权限限制下。

所以我想做的是按他们的值( 高到低) 排序项目,然后选择项目只要 Knapsack的重量小于 WEIGHT_MAX 。

i.e 像这样


while( temp_weight <= WEIGHT_MAX && i <= INDEX_MAX )
{
 if ( temp_weight + W[i]> WEIGHT_MAX ) { i++; continue;}
 temp_weight += W[i];
 value += V[i];
 i++;
}

为什么该算法错误?

时间: 作者:

考虑以下排序元素:

Vi={10,5,5,5,5,5,5 }

Wi={4,1,1,1,1,1,1 }

如果WEIGHT_MAX是 4,那么你可以选择V=10元素( 总计值 10 ) 。 但最佳解是 4个带有 V=5 ( 总计值 20 )的元素。

这就是为什么你的算法不会导致。

解决该问题的几种算法: http://en.wikipedia.org/wiki/Knapsack_problem

作者:
...