algorithm - 一种打包算法......有点

Question

给定一个项目数组，每个项目都有一个值和成本，什么是最好的算法来确定达到最小值所需的项目最低成本？ 例如:

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

请注意，最后的整体值(value):成本比率是无关紧要的(A + A 会给你最好的性价比，但 A + B + B 是一个更便宜的选择，达到最小值)。

Answer 1

这就是背包问题。 (也就是说，这个问题的决策版本与背包问题的决策版本相同，尽管背包问题的优化版本通常有不同的表述。)它是 NP-hard(这意味着没有已知的算法是“大小”中的多项式 - 输入中的位数)。但是，如果您的数字很小(例如，输入中最大的“值”；成本无关紧要)，那么有一个简单的动态规划解决方案。

让 best[v] 成为获得(准确)v 值的最小成本。然后您可以计算所有 v 的值 best[]，方法是(将所有 best[v] 初始化为无穷大并且):

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

然后查看 best[v] 的值，直到您想要的最小值加上最大值；最小的那些会给你成本。

如果您想要实际项目(而不仅仅是最低成本)，您可以维护一些额外的数据，或者只查看 best[] 数组并从中进行推断。