3

こんにちは私は私が変更を取り戻すことができる方法がいくつあるかを見つけるアルゴリズムを作成しようとしています。しかし、私は実装を正しく行うことができません。私は4を取得し続けますが、6を取得する必要があり、その理由がわかりません。

これはC＃での私の実装であり、 http：//www.algorithmist.com/index.php/Coin_Changeの擬似コードから作成されます。

     private static int[] S = { 1, 2, 5 };
        private static void Main(string[] args)
        {
            int amount = 7;
            int ways = count2(amount, S.Length);
            Console.WriteLine("Ways to make change for " + amount + " kr: " + ways.ToString());
            Console.ReadLine();
        }    
static int count2(int n, int m)
        {
        int[,] table = new int[n,m];

        for (int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                // Rules
                // 1: table[0,0] or table[0,x] = 1
                // 2: talbe[i <= -1, x] = 0
                // 3: table[x, j <= -1] = 0

                int total = 0;

                // first sub-problem
                // count(n, m-1)
                if (i == 0) // rule 1
                    total += 1;
                else if (i <= -1) // rule 2
                    total += 0;
                else if (j - 1 <= -1)
                    total += 0;
                else
                    total += table[i, j-1];

                // second sub-problem
                // count(n-S[m], m)
                if (j - 1 <= -1) // rule 3
                    total += 0;
                else if (i - S[j - 1] == 0) // rule 1
                    total += 1;
                else if (i - S[j - 1] <= -1) // rule 2
                    total += 0;
                else
                    total += table[i - S[j-1], j];

                table[i, j] = total;
            }
        }
        return table[n-1, m-1];
    }
4

5 に答える 5

5

深夜の退屈から（そして、はい、これは間違いなく洗練する必要があります）...再帰、linq、yieldを一度に使用し、コード行と同じ数の中括弧があるので、私は非常に逆に満足していますそれ...

    static IEnumerable<List<int>> GetChange(int target, IQueryable<int> coins)
    {
        var availableCoins = from c in coins where c <= target select c;
        if (!availableCoins.Any())
        {
            yield return new List<int>();
        }
        else
        {
            foreach (var thisCoin in availableCoins)
            {
                foreach (var result in GetChange(target - thisCoin, from c in availableCoins where c <= thisCoin select c))
                {
                    result.Add(thisCoin);
                    yield return result;
                }
            }
        }
    }
于 2010-10-14T00:42:06.890 に答える
2

これが正常に機能するアルゴリズムです。緑色の「再生」矢印を押して実行します。 http://www.exorithm.com/algorithm/view/make_change

主な問題は、アルゴリズムのループを-1から開始する必要があることだと思います。再帰的に書く方がずっとわかりやすいと思いますが、楽しい練習でした。

于 2010-10-14T04:35:17.183 に答える
2

アルゴリズムがどのように機能するかを説明しておくと便利です。コメントがなく、変数の名前が、、、だけnの場合m、i目的を理解するのは非常に困難です。coinTypeたとえば、さまざまな種類のコインを反復処理する場合など、よりわかりやすい名前を使用する必要があります。

しかし、私にはかなり疑わしい場所がいくつかあります。たとえば、変数iとj範囲内の値を反復処理する1 .. mか、1 .. n-それらは常に正になります。これは、ルール2と3が実行できないことを意味します。

// ...
  else if (i <= -1)     // <- can never be 'true'
    total += 0; 
  else if (j - 1 <= -1) // <- 'true' when 'j == 0'
// ...
  if (j - 1 <= -1)      // <- can never be 'true'
// ...

i同様に-1、以下になることはありません。j

于 2010-10-13T23:31:44.333 に答える
1

table [i、j]は、コイン{0、1、2、...、j-1}のみを使用して正確に1セントの値を達成するための方法の数を格納することを意味すると思います。

基本的に、whileループの内側の部分は、table [i、j]は、コインjを使用せずにiの値に到達する方法の数に、atを使用してiの値を達成する方法の数に等しくなければならないことを示しています。値S[j]の少なくとも1つのコイン。したがって、境界の場合を除いて、値はtable [i、j --1] + table [i --S [j]、j]です。合計の最初の部分は、値S [j]のコインを使用せずにiに到達する方法の数であり、2番目の部分は、値S[j]のコインを少なくとも1つ使用してiに到達する方法の数です。

変更してみてください：

        // second sub-problem
        // count(n-S[m], m)
        if (j - 1 <= -1) // rule 3
            total += 0;
        else if (i - S[j - 1] == 0) // rule 1
            total += 1;
        else if (i - S[j - 1] <= -1) // rule 2
            total += 0;
        else
            total += table[i - S[j-1], j];

に：

        // second sub-problem
        // count(n-S[m], m)
        if (i - S[j] == 0) // rule 1
            total += 1;
        else if (i - S[j] < 0) // rule 2
            total += 0;
        else
            total += table[i - S[j], j];

参考までに、（j <= -1）ではなく（j <0）のようなものを書くのが標準です。

于 2010-10-14T00:25:26.883 に答える
1

いくつかの観察。

count1）関数を擬似コードから別のサブルーチンに移動すると、コードがはるかに単純になります（エラーが発生しにくくなります） 。このようなもの（リンクからの擬似コードに基づく）

func count(table, i, j)
  if ( i == 0 ) 
    return 1
  if ( i < 0 )
    return 0
  if ( j <= 0 and i >= 1 )
    return 0

  return table[i][j]
end

その後、あなたはただすることができます

table[i][j] = count(table, i, j - 1) + count(table, i - S[j], j)

あなたの内側のループで。

2）ではcount2、最初のループがn - 1何度も発生します。つまり、n == 1ループ本体に入らず、解決策が見つからないということです。内側のループについても同じです。コインが1つしかない場合、解決策は見つかりません。

于 2010-10-13T23:37:46.780 に答える