最大限度地减少转手的硬币数量[关闭]

3 回答

• 1

  最小化总和到给定数量的硬币数量是Knapsack Problem的版本 .

  你的问题是尽量减少 coins(S1) + coins(S2) （你是职员的职员） S1 - S2 = S （你应该支付的金额） . 所以你想解决 S 和 Smax 之间所有变化值的背包问题（知道 coins(x) 的所有值），然后求解：

  min coins(S1) + coins(S2)
  under constraints
    S1 - S2 = S
    S1 in [S, Smax]
  

  这可以通过简单的枚举（测试S1的每个可能值）来解决 .

  现在的问题是确定 Smax 的值 .

  我是 not sure about this 但我认为，因为你最大的硬币是2美元，如果你给店员大于S 2 $的东西，你将不会有更少的硬币转移 . 所以我的猜测是 Smax = S + 2$ ，但我邀请你多考虑一下 .

  回复于 2024-04-20T21:07:14+08:00
• 0

  我最近在my blog解决了这个问题 . 在这里's the ending, but you' ll必须阅读整个博客条目才有意义：

  (define (floupia price coins)
    (if (positive? (modulo price (apply gcd coins)))
        (error 'floupia "infeasible")
        (let ((coins (append coins (map negate coins))))
          (let loop ((n 1))
            (let ((xs (filter (lambda (xs) (= (sum xs) price))
                              (combinations-with-replacement n coins))))
              (if (null? xs) (loop (+ n 1)) xs))))))
  

  基本的想法是首先看一个硬币是否可以支付账单，然后是两个硬币，然后是三个，依此类推，当你找到最小的解决方案时停止 . 在每个步骤考虑所有硬币的所有可能组合，与替换，以查看是否有解决方案，将收到的更改视为负硬币 . 例如，对于面值为1,3,7,31和153的硬币，以及17的目标价格，有一个5硬币的解决方案，包括支付三个7硬币并收回单个1硬币和3个硬币在改变，但更有效的解决方案是支付一个31硬币和收到两个7硬币的变化 .

  回复于 2024-04-20T21:07:14+08:00
• 0

  这是通常使用启发式搜索解决的类型的NP完全问题 . 相关的启发式是首先尝试更大的面额 .

  回复于 2024-04-20T21:07:14+08:00