4

假设我想获得等于给定值的所有纸币/硬币面额组合，同时也给出一组可用面额。

例如，因为(change 14 #{1 2 5 10})我希望

(
    {10 1, 5 0, 2 2, 1 0}
    {10 1, 5 0, 2 1, 1 2}
    {10 0, 5 2, 2 2, 1 0}
    {10 0, 5 2, 2 1, 1 2}
    ;; ...
)

我的尝试是

(defn change [amount denominations]
  (let [dens (sort > denominations)
        vars (repeatedly (count dens) lvar)]
    (run* [q]
      (== q (zipmap dens vars))
      (everyg #(fd/in % (fd/interval 0 amount)) vars)
      (== amount (apply + (map * dens vars))))))

但自然最后一行不起作用。我还没有找到一种方法来reduce对vars序列进行某种处理，或者其他一些方法来设置对每个 lvar 无效但对整体无效的目标（同时还对外部值进行一些操作，amount在denominations这个例子中）。

4

1 回答 1

2

我还没有找到一种 [...] 方法来设置对每个 lvar 无效但对整体无效的目标（同时在此示例中还对外部值、金额和面额进行一些操作）。

一种方法是定义一个递归关系函数，该函数采用逻辑vars、面额和期望sum，并用于conso为每对vars和dens项目设置目标：

(defn productsumo [vars dens sum]
  (fresh [vhead vtail dhead dtail product run-sum]
    (conde
      [(emptyo vars) (== sum 0)]
      [(conso vhead vtail vars)
       (conso dhead dtail dens)
       (fd/* vhead dhead product)
       (fd/+ product run-sum sum)
       (productsumo vtail dtail run-sum)])))

注意fresh这里的逻辑变量 and 的头部和尾部vars，densaproduct存储每个“pass”的头部的乘积，以及一个run-sum变量将用于约束所有乘积的总和，使其等于sum. 和 递归的结合conso使我们可以为整个vars和设定目标dens。

然后将其插入您现有的功能：

(defn change [amount denoms]
  (let [dens (sort > denoms)
        vars (repeatedly (count dens) lvar)]
    (run* [q]
      (== q (zipmap dens vars))
      (everyg #(fd/in % (fd/interval 0 amount)) vars)
      (productsumo vars dens amount))))

最后得到答案：

(change 14 #{1 2 5 10})
=>
({10 0, 5 0, 2 0, 1 14}
 {10 1, 5 0, 2 0, 1 4}
 {10 0, 5 1, 2 0, 1 9}
 {10 0, 5 0, 2 1, 1 12}
 {10 1, 5 0, 2 1, 1 2}
 {10 1, 5 0, 2 2, 1 0}
 {10 0, 5 0, 2 2, 1 10}
 {10 0, 5 2, 2 0, 1 4}
 {10 0, 5 1, 2 1, 1 7}
 {10 0, 5 0, 2 3, 1 8}
 {10 0, 5 0, 2 4, 1 6}
 {10 0, 5 1, 2 2, 1 5}
 {10 0, 5 0, 2 5, 1 4}
 {10 0, 5 2, 2 1, 1 2}
 {10 0, 5 0, 2 6, 1 2}
 {10 0, 5 1, 2 3, 1 3}
 {10 0, 5 0, 2 7, 1 0}
 {10 0, 5 2, 2 2, 1 0}
 {10 0, 5 1, 2 4, 1 1})

我怀疑可能有一个更简洁/优雅的解决方案，但这有效。

于 2018-01-21T19:35:15.903 回答