5

再帰スキームに関するこのブログから、組織型を理解しようとしています。ブログに記載されているように、変更を行う問題を解決するために例を実行しているときに問題に直面しています。

両替問題は、通貨の額面を取り、特定の金額を作成するために必要なコインの最小数を見つけようとします。以下のコードはブログから取得したもので、答えを計算する必要があります。

{-# LANGUAGE DeriveFunctor #-}

module Main where

import Control.Arrow ( (>>>) )
import Data.List ( partition )
import Prelude hiding (lookup)

newtype Term f = In {out :: f (Term f)}

data Attr f a = Attr
  { attribute :: a
  , hole :: f (Attr f a)
  }

type CVAlgebra f a = f (Attr f a) -> a

histo :: Functor f => CVAlgebra f a -> Term f -> a
histo h = out >>> fmap worker >>> h
 where
  worker t = Attr (histo h t) (fmap worker (out t))

type Cent = Int

coins :: [Cent]
coins = [50, 25, 10, 5, 1]

data Nat a
  = Zero
  | Next a
  deriving (Functor)

-- Convert from a natural number to its foldable equivalent, and vice versa.
expand :: Int -> Term Nat
expand 0 = In Zero
expand n = In (Next (expand (n - 1)))

compress :: Nat (Attr Nat a) -> Int
compress Zero = 0
compress (Next (Attr _ x)) = 1 + compress x

change :: Cent -> Int
change amt = histo go (expand amt)
 where
  go :: Nat (Attr Nat Int) -> Int
  go Zero = 1
  go curr@(Next attr) =
    let given = compress curr
        validCoins = filter (<= given) coins
        remaining = map (given -) validCoins
        (zeroes, toProcess) = partition (== 0) remaining
        results = sum (map (lookup attr) toProcess)
     in length zeroes + results

lookup :: Attr Nat a -> Int -> a
lookup cache 0 = attribute cache
lookup cache n = lookup inner (n - 1) where (Next inner) = hole cache

これで評価change 10すると 3 になります。

これは... 10 の値のコイン 1 枚を使用して 10 を作ることができるため、間違っています。

だから私はそれが、与えられた金額を稼ぐことができる方法の最大数を見つけるコインチェンジ問題を解決しているのかもしれないと考えました. たとえば、 、 、 、 の 4 つの方法で 10 を{ 1, 1, ... 10 times }作成{ 1, 1, 1, 1, 5}でき{ 5, 5 }ます{ 10 }。

では、このコードの何が問題になっているのでしょうか? 問題を解決する上でどこが間違っていますか？

TLDR

再帰スキームに関するこのブログの上記のコードは、金額を変更する最小または最大の方法を見つけていません。なぜ機能しないのですか？

4

3 に答える 3

1

このプログラムには 2 つの問題があります。そのうちの 1 つは修正方法を知っていますが、もう 1 つは明らかに再帰スキームの知識が必要です。

私が修正できるのは、キャッシュで間違った値を検索していることです。given = 10もちろん、いつ、validCoins = [10,5,1]そしてそう私たちは見つけます(zeroes, toProcess) = ([0], [5,9])。これまでのところ、1 セント硬貨を直接渡すか、1 セント硬貨を渡して残りの 5 セントを両替するか、1 セントを渡して残りの 9 セントを両替することができます。しかし、私たちが書くときlookup 9 attr、私たちは「いつまで歴史の9つのステップを見る」と言っていcurr = 1ますcurr = 9. その結果、ほぼすべてのケースで大幅に過小評価されています。偶数change 100はわずか 16 ですが、Google 検索では正しい結果は 292 であると主張されています (今日、自分で実装してこれを検証していません)。

これを修正する同等の方法がいくつかあります。最小の差分は置き換えることです

results = sum (map (lookup attr)) toProcess)

と

results = sum (map (lookup attr . (given -)) toProcess)

2 つ目の問題は、キャッシュ内の値が間違っていることです。質問へのコメントで述べたように、これは同じ宗派の異なる順序を質問への個別の回答としてカウントします。最初の問題を修正した後、この 2 番目の問題が現れる最低の入力は 7 で、結果は正しくありませんchange 7 = 3。試してみるchange 100と、計算にどれくらいの時間がかかるかわかりません。本来よりもはるかに長く、おそらく非常に長い時間です。しかし、 のような控えめな値でも、本来change 30あるべきよりもはるかに大きな数値が得られます。

アルゴリズムを大幅に作り直さない限り、これを修正する方法はありません。この問題に対する従来の動的計画法のソリューションでは、特定の順序でソリューションを生成する必要があるため、二重カウントを回避できます。つまり、最初に使用する 10 セント硬貨の数 (ここでは 0 または 1) を決定し、次に 10セント硬貨を使用せずに残りの金額を変更する方法を計算します。ここでそのアイデアをどのように機能させるかはわかりません。キャッシュ キーは、目標金額と許可されたコインのセットの両方を含めて、より大きくする必要があります。

于 2021-10-20T12:38:03.303 に答える