最大化购买的商品数量
我们有一个数组 Ai 表示商品 i 的价格。
我们有 k 数量的货币，我们可以购买第一个项目 n 次，第二个项目 n-1 次，第三个项目 n-2 次，依此类推。找出可以购买的最大物品数量。
1<= n <= 10^4
1<= Ai <= 10^6
1 <= k <= 10^9
我以为
这是一个 0/1 背包的情况，但它会超出内存，因为总和非常大。有没有我看不到的贪婪直接算法？我不需要代码，只需解决这个问题的方法就会有很大的帮助。
We are given an array Ai denoting the price of item i.
We have k amount of currency and we can buy the first item n times, second item n-1 times, third item n-2 times and so on. Find the maximum number of items which can be bought.
1<= n <= 10^4
1<= Ai <= 10^6
1 <= k <= 10^9
What I thought
I thought its a case of 0/1 Knapsack but it will exceed the memory as the sum is very large. Is there any greedy straight forward algorithm I can't see? I don't need the code, just approach towards solving this problem will be of great help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您想最大化可以购买的物品数量，则不会遇到背包问题（在背包问题中，每个物品都有一定的价值或重量，并且您希望最大化所包装物品的总重量）。贪婪的解决方案应该适用于您的问题。只需根据物品的价格对物品进行排序（你必须记住记录每件物品可以购买多少次，例如成对购买），然后购买最便宜的，直到你用完钱。这应该会给你一个 O(nlog(n)) 的解决方案。
If you want to maximize the number of items you can buy you don't have a Knapsack problem (in a Knapsack problem each item has some value or weight and you want to maximize the overall weight of the items you pack). A greedy solution should work for your problem. Just sort the items according to their price (you have to remember to keep track of how many times you can buy each item, e.g. using pairs) and then buy the cheapest available until you run out of money. This should give you an O(nlog(n)) solution.