最大限度地增加购买物品的数量

Question

我们得到一个表示i项价格的数组Ai。

我们有k个货币，我们可以购买第一个项目n倍，第二个项目n-1倍，第三项n-2倍，等等。找到可以购买的物品的最大数量。

1<= n <= 10^4              
1<= Ai <= 10^6          
1 <= k <= 10^9

我的想法

我以为这是0/1背包的情况，但由于和很大，它会超过内存。有什么我看不见的贪婪的直进算法吗？我不需要代码，解决这个问题的方法会有很大的帮助。

Answer 1

如果你想要最大限度地增加你能买到的物品的数量，你就没有背包问题(在背包问题中，每个物品都有一些价值或重量，你想要最大化你包装的物品的整体重量)。一个贪婪的解决方案应该能解决你的问题。只需根据商品的价格进行排序(你必须记住你能买到每一件物品多少次，例如用对)，然后买最便宜的，直到你用完钱为止。这将为您提供一个O(nlog(n))解决方案。