最大硬币分区-Java 学习之路

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

给定一个值为v1，...，vn的硬币系统，有限的硬币a1，...，an和我们需要支付的金额 . 我们正在寻找一种算法来计算分区x1，...，xn（其中0 <= xi <= ai），其中x1 * v1 x2 * v2 ... xn * vn> = s，使得和x1 . .. xn - R（r）最大化，其中r是变化，即r = x1 * v1 x2 * v2 ... xn * vn - s和R（r）是从收银员返回的硬币数量 . 我们假设出纳员拥有无限量的所有硬币并且总是返回最小数量的硬币（例如使用SCHOENING等人中解释的贪婪算法） . 我们还需要确保没有钱的变化，所以最好的解决方案不是简单地给所有的钱（因为在这种情况下解决方案总是最优的） .

感谢您的创意投入！

1 回答

1
如果我理解正确，这基本上是subset sum的变体 . 如果我们假设你有每个硬币中的一个（每个 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 ，你有 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 向量应该相当容易 . 如果您需要更多详细信息，请与我们联系 .
回复于 2024-04-28T00:16:59+08:00

最大硬币分区

1 回答

相关问题