5

自从昨天站在超市的销售点，再次尝试启发式地找到我的硬币的最佳分区，同时试图忽略我身后不耐烦和紧张的队列，我一直在思考潜在的算法问题：

给定一个价值为 v 1 ,...,v n的硬币系统，有限数量的硬币 a 1 ,...,a n以及我们需要支付的金额 s。我们正在寻找一种算法来计算分区 x 1 ,...,x n (with 0<=x i <=a i ) with x 1 *v 1 +x 2 *v 2 +...+x n *v n >= s 使得总和 x 1 +...+x n - R(r) 最大化，其中 r 是变化，即 r = x 1 *v 1 +x 2 *v 2 +。 ..+xn *v n - s 和 R(r) 是从收银员返回的硬币数量。我们假设收银员拥有无限数量的所有硬币，并且总是返还最少数量的硬币（例如使用 SCHOENING 等人解释的贪婪算法）。我们还需要确保没有换钱，所以最好的解决方案不是简单地给所有的钱（因为在这种情况下解决方案总是最优的）。

感谢您的创意输入！

4

1 回答 1

1

如果我理解正确，这基本上是subset sum的变体。如果我们假设您每个硬币都有 1 个（a[i] = 1对于 each i），那么您可以像这样解决它：

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
        sum[j] |= sum[j - v[i]]

然后找到第一个k >= s和sum[k]是true。您可以通过跟踪每个硬币的贡献来获得实际使用的硬币sum[j]。您获得的金额越接近s使用您的硬币，零钱就越少，这就是您所追求的。

现在你没有每个硬币 1 i，你有a[i]每个硬币i。我建议这样做：

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
       for k = 1 to a[i] do
           if j - k*v[i] >= 0 do
               sum[j] |= sum[j - k*v[i]] <- use coin i k times

x从中获取向量应该相当容易。如果您需要更多详细信息，请告诉我。

于 2011-02-09T23:55:13.300 回答