最大硬币分配

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_{2*v2+...+xn*vn - s 和 R(r) 是从返回的硬币数量收银员。我们假设收银员拥有无限数量的所有硬币，并且总是归还最小数量的硬币（例如通过使用 SCHOENING 等人中解释的贪婪算法）。我们还需要确保没有金钱变化，因此最好的解决方案不是简单地提供所有资金（因为在这种情况下解决方案始终是最佳的）。}

感谢您的创意投入！

Answer 1

如果我理解正确的话，这基本上是 子集和 的变体。如果我们假设每种硬币都有 1 个（每个 i 都有 a[i] = 1），那么您可以这样解决：

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 向量应该相当容易。如果您需要更多详细信息，请告诉我。