最大硬币分区

Question

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

给定一个值为v ₁,...,v _n的硬币系统,有限的硬币库存a ₁,...,a _n和我们需要支付的金额.我们正在寻找一种算法来计算分区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使用你的硬币，找零就越少，这就是你所追求的。

现在你不再拥有每枚硬币 1 个i，而是a[i]每枚硬币都有 1 个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从中获得向量应该相当容易。如果您需要更多详细信息，请告诉我。