APL 中的硬币计数

Question

下面的函数 Count 计算总计达到给定数量的最少硬币数量。

∇ R ← d AppendQuotRem qrs; oldR; q; r
    oldR ← 2 ⊃ (⍴qrs) ⊃ qrs
    q ← ⌊oldR ÷ d
    r ← oldR - d × q
    R ← qrs , ,⊂(q r)
∇

∇ R ← Count amount; ds; qrs; qs
    ds ← 1 5 10 25 50  ⍝ coin denominations in cents
    qrs ← ⊃AppendQuotRem/ ds , ⊂,⊂(0 amount)
    qs ← 1 ⊃¨ qrs
    R ← ds ,[0.5] ⌽1 ↓ qs
∇

对于每一种面额，我计算商和余数。余数用于涉及下一个面额的计算。有没有更短 and/or 更直接的方法来解决问题？

Answer 1

change-making problem is actually quite hard. A full APL approach is included in the dfns workspace.

你的算法是贪婪的，它对某些硬币面额的集合给出了错误的结果。它恰好适用于您在示例中使用的集合。让我们修改您的 Count 函数：

∇ R ← Count134 amount; ds; qrs; qs
    ds ← 1 3 4  ⍝ coin denominations in cents
    qrs ← ⊃AppendQuotRem/ ds , ⊂,⊂(0 amount)
    qs ← 1 ⊃¨ qrs
    R ← ds ,[0.5] ⌽1 ↓ qs
∇
      Count134 6
1 3 4
2 0 1

这使用三个硬币，但正确答案是两个 3 美分硬币：

1 3 4
0 2 0

话虽这么说，但设计常见的造币系统时，贪心算法会产生最佳结果。因此，这是您的代码的简化：

∇ R ← d AppendQuotRem qrs; oldR; q; r
    oldR ← 1 ↑ qrs
    q ← ⌊oldR ÷ d
    r ← d | oldR
    R ← r , q , 1 ↓ qrs
∇

∇ R ← Count amount; ds
    ds ← 1 5 10 25 50  ⍝ coin denominations in cents
    R ← ds ,[0.5] ⊃AppendQuotRem/ 1 ↓ ds , amount
∇

Try it online!

Answer 2

贪心算法，货币价值为 100 50 20 10 5 1 个单位。

  ∇r←Greedy w;i;d;k;x;l
  r←⍬⋄i←1⋄d←100 50 20 10 5 1⋄l←≢d
  r←r,k←⌊w÷x←d[i]⋄w-←k×x⋄→2×⍳l≥i+←1
  r←2 l⍴d,r
  ∇
  
  Prova←{+/⍵[1;]×⍵[2;]}
  m←Greedy 125
  m
100 50 20 10 5 1
  1  0  1  0 1 0
  Prova m
125

APL 中的硬币计数

Counting coins in APL

greedy

apl

coin-change