3

我们有 N 金币和 M 银币。有k个物品，每个都有一定的成本，A金币和B银币，其中A或B也可以为零。

购买最大数量商品的算法是什么？

4

3 回答 3

4

这是背包问题吗？

你描述的问题不是背包问题。在这里，您只想最大化项目数量，而不是它们的总成本。在背包问题中，您感兴趣的是最大化总成本，同时尊重麻袋的容量。换句话说，你想抓住最有价值的物品，可以装在你的袋子里。您并不真正关心它们中有多少，而只关心它们是最有价值的！

下面，我们将讨论问题的两种变体：

  1. 单一货币——金银币可相互兑换
  2. 多种正交货币——金币不能转换成白银。

单一货币变体

假设你只被允许花费 N 金币和 M 银币，下面是一个应该可以工作的算法：

1. Sort the items by cost, from cheapest to the most expensive.
2. totalCost = 0; i = 1
3. while totalCost <= goldToCost(N) + silverToCost(M) + item[i].cost
4.    totalCost = totalCost + items[i].cost
5.    i++
6. endWhile
7. return i

由于排序，该算法只需要O(nlogn)时间。

多币种

上述解决方案假设两种货币可以相互转换。该问题的另一个变体涉及正交货币，其中两种货币不能相互兑换。在这种情况下，所有成本都将被指定为向量。

为了解决这个问题，使用了动态规划算法。我们需要询问是否表现出以下两个特征：

  1. 最优子结构。问题的最优解是否源自其子问题的最优解？例如，S(M, N)我们可以使用 M 金币和 N 银币购买的最大物品数量。我们可以S(M, N)使用递归关系推导吗？
  2. 重叠的子问题。S(M, N) 的子问题是否反复用于计算更大的子问题？

想象一个有 N 行 M 列的二维表。这

+---+---+---+---+---+-----+---+
|   | 0 | 1 | 2 | 3 | ... | N |
+---+---+---+---+---+-----+---+
| 0 |   |   |   |   |     |   |
| 1 |   |   |   |   |     |   |
| 2 |   |   |   |   | ... |   |
| 3 |   |   |   |   |     |   |
| : |   |   |   |   |     |   |
| M |   |   |   |   |     |   |
+---+---+---+---+---+-----+---+

我们的算法基本上会填写这张表。在行i、列j S[i, j]中，使用 i 金币和 j 银币可以购买的最大物品数量。

为了完成该表，我们可以使用两个按字典顺序排序的数组，I并且D. 首先，gold 作为主排序键，silver 次要。第二，白银是主要的，黄金是次要的。填写第 0 行和第 0 列是直截了当的。然后我们串联遍历这两个排序的数组，然后我们可以使用下面的递归来完成表格

S[0, 0] = 0
S[i, j] = 0   if i < 0 or j < 0 
S[i, j] = max(S[i-1,j-1] + d[i-1,j-1], S[i-1,j] + d[i-1,j], S[i,j-1] + d[i,j-1])

d[i*,j*]您可以使用 购买的其他物品数量在哪里<i,j> - <i*, j*>，其中<i*, j*>之一在哪里{<i-1, j-1>, <i-1, j>, <i, j-1>}。换句话说，你可以用剩下的钱买多少。计算这个的搜索涉及对两个按字典顺序排序的序列（I或D）之一进行二进制搜索。

该解决方案需要O((MN + n)logn)时间来计算并使用O(MN + n)空间。

于 2012-05-09T12:46:21.250 回答
4

在这个问题中，每个项目都有一个二维成本。让项目 i 的成本为 c[i] = < a, b > 其中 a 是金币的成本，b 是银币的成本。

现在可以部分订购物品，以便物品 i 比物品 j“不贵”，如果

c[i] = <a, b>    c[j] = <a', b'>  and    a <= a' AND b <= b'

请注意，这是部分订单。两个项目 <1, 2> 和 <2, 1> 在这个偏序中是不可比较的；两者都不比另一个贵。

现在很清楚，贪心算法可以安全地购买物品，只要它们与剩余的所有其他物品相比“不贵”，但是当有多个不可比较的物品可用时，可以进行更多分析（例如搜索）需要。

例如，如果成本是

 <1, 1>
 <2, 1>
 <1, 2>
 <3, 3>

这导致了这个部分顺序：

        <1, 1>
       /      \
     <2, 1>   <1, 2>
         \   /
         <3, 3>

（最贵的物品在底部）。贪心算法会先购买<1, 1>。之后，<2, 1> 和 <1, 2> 都是可行的购买选项。如果算法选择购买 <2, 1>，那么下一个要购买的是 <1, 2>，因为它现在并不比所有其他剩余物品 (<3, 3>) 贵。

简单的贪心算法可能会失败。设置<2, 1>, <1, 2>, <3, 0>，初始硬币数量gold = 4, silver = 2，最优解是<1, 2> 和<3, 0> , 但首先购买 <2, 1> 会导致只能购买该物品（购买时留下的 <2, 1> 硬币不允许购买其余两个物品中的任何一个）。

我会接近这个购买构建部分订单结构，然后执行回溯搜索。如果时间限制不允许完全回溯，我将使用有限回溯作为其他贪婪算法的启发式方法。

于 2012-05-10T06:13:24.470 回答
-2

没有“算法”。

您正在描述背包问题的一个版本，这是一个众所周知的 NP 完全问题。对于问题的 SMALL 版本，使用小的 N、M 和 k，您只需遍历所有不同的组合。对于较大的版本，没有已知的方法可以找到计算时间少于宇宙生命周期的“最佳”解决方案。

最接近解决这个问题的方法涉及一个称为线性规划的领域。这......不是一件简单的事情，但如果你愿意，你可以去阅读它。

于 2012-05-08T23:17:31.893 回答