最大化购买的物品数量
Maximize the number of items bought
我们有一个数组 Ai 表示第 i 项的价格。
我们有k个货币，我们可以购买第一个物品n次，第二个物品n-1次，第三个物品n-2次等等。找出最多可以购买的物品数量。
1<= n <= 10^4
1<= Ai <= 10^6
1 <= k <= 10^9
我的想法
我以为是0/1 Knapsack的情况，但总和很大，会超出内存。有没有我看不到的贪婪直接算法？我不需要代码，只要解决这个问题的方法就会有很大帮助。
如果您想最大化可以购买的物品数量，则没有背包问题（在背包问题中，每件物品都有一定的价值或重量，并且您想要最大化所打包物品的总重量).贪婪的解决方案应该适用于您的问题。只需根据价格对商品进行排序（您必须记住跟踪每件商品可以购买多少次，例如使用成对购买），然后购买最便宜的商品，直到 运行 没钱。这应该给你一个 O(nlog(n)) 解决方案。
我们有一个数组 Ai 表示第 i 项的价格。
我们有k个货币，我们可以购买第一个物品n次，第二个物品n-1次，第三个物品n-2次等等。找出最多可以购买的物品数量。
1<= n <= 10^4
1<= Ai <= 10^6
1 <= k <= 10^9
我的想法
我以为是0/1 Knapsack的情况，但总和很大，会超出内存。有没有我看不到的贪婪直接算法？我不需要代码，只要解决这个问题的方法就会有很大帮助。
如果您想最大化可以购买的物品数量，则没有背包问题（在背包问题中，每件物品都有一定的价值或重量，并且您想要最大化所打包物品的总重量).贪婪的解决方案应该适用于您的问题。只需根据价格对商品进行排序（您必须记住跟踪每件商品可以购买多少次，例如使用成对购买），然后购买最便宜的商品，直到 运行 没钱。这应该给你一个 O(nlog(n)) 解决方案。