一种打包算法......种类

鉴于项目的数组,每个有value和cost,什么是最好的算法确定达到以最小的成本最低值所需的项目？例如:

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

请注意,总体价值:最终的成本比率是无关紧要的(A + A会给你最好的物有所值,但是A + B + B是一个更便宜的选择,达到最低价值).

这是背包问题.(也就是说,这个问题的决定版本与背包问题的决策版本相同,虽然背包问题的优化版本通常有不同的说法.)它是NP难的(这意味着没有算法是已知的"大小"中的多项式 - 输入中的位数 - .但是如果你的数字很小(输入中最大的"值",比如说;成本无关紧要),那么就有一个简单的动态编程解决方案.

设最佳[v]为获得(精确)v值的最小成本.然后,您可以计算所有v的最佳值[](将所有最佳[v]初始化为无穷大):

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

然后查看最佳值[v],以获得您想要的最小值加上最大值; 最小的那些会给你带来成本.

如果你想要实际项目(而不仅仅是最低成本),你可以保留一些额外的数据,或者只查看最佳[] s数组并从中推断.