algorithm - 如果成本与使用每个数字相关联，则找出最大数量

Question

我已经得到了我所有的钱。现在我知道写下每个数字(1 到 9)所需的成本。那么如何创建最大数量呢？这个问题有动态规划的方法吗？

例子:

可用的总金额 = 2
每个数字(1 到 9)的成本 = 9, 11, 1, 12, 5, 8, 9, 10, 6
输出:33

Answer 1

我认为你不需要动态规划，只需执行以下操作:

• 尽可能多地选择价格最低的号码。
• 现在您有了一个数字(仅由一种数字组成)。
• 用你能负担得起的最大数字替换第一个数字
• 如果你还有钱，对第二个、第三个等做同样的事情，直到你的钱用完。

为什么会这样:

考虑 11111 > 9999 和 91111 > 88888，或者换句话说，最好是:

• 选择尽可能多的数字，这是通过选择最便宜的数字来完成的。
• 然后用您能负担得起的最高值(value)的数字替换这些数字，从左边开始(这总是比选择一些更昂贵的数字开始更好)。

优化:

为了有效地做到这一点，丢弃任何比更大数字花费更多的数字:(因为选择那个数字而不是具有更大值(value)的更便宜的数字从来都不是一个好主意)

Given:
9, 11, 1, 12, 5, 8, 9, 10, 6
Removing all those where I put an X:
X, X, 1, X, 5, X, X, X, 6
So:
1, 5, 6

现在您可以对其进行二进制搜索(只需记住哪个数字来自哪个值)(尽管只有 9 位数字，二进制搜索并不能真正为已经很短的运行时间创造奇迹)。

运行时间:

O(n)(有或没有优化，因为 9 是常量)