我已经得到了我所有的钱。现在我知道写下每个数字(1 到 9)所需的成本。那么如何创建最大数量呢？这个问题有动态规划的方法吗？
例子:
可用的总金额 = 2
每个数字(1 到 9)的成本 = 9, 11, 1, 12, 5, 8, 9, 10, 6
输出:33
最佳答案
我认为你不需要动态规划，只需执行以下操作:
- 尽可能多地选择价格最低的号码。
- 现在您有了一个数字(仅由一种数字组成)。
- 用你能负担得起的最大数字替换第一个数字
- 如果你还有钱，对第二个、第三个等做同样的事情，直到你的钱用完。
为什么会这样:
考虑 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 是常量)
关于algorithm - 如果成本与使用每个数字相关联，则找出最大数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19055840/