algorithm - 最大硬币分区

Question

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

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

感谢您的创意投入!

Answer 1

如果我没理解错的话，这基本上是subset sum的变体。 .如果我们假设每个硬币都有 1 个(a[i] = 1 代表每个 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，零钱就越少，这就是您所追求的。

现在你没有每个硬币 i 的 1，你有每个硬币 i 的 a[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 向量应该相当容易。如果您需要更多详细信息，请告诉我。