0

コインの両替問題に対するボトムアップのアプローチを構築しています。要求された変更を提供するために必要な最小数のコインを提供する必要があります。指定された金種が値を形成できないため、変更を指定できなかった可能性があります。

たとえば、指定された金種が {4, 8} で、5 の変更を要求した場合、5 を発行することは不可能です。以下のプログラムを作成しましたが、要求された変更を形成することが不可能でない限り、ほとんどの状況でうまく機能します。 . たとえば、金種がちょうど {4} の場合に 5 をリクエストすると、偽の 1 つが返されます。この問題を解決するにはどうすればよいですか?

ここで、P は要求された変更を表し、S はインデックス 0 から S - 1 までの配列 denominations[] に格納されている金種の数です。dp は -1 に初期化された計算用の 2 次元配列です。

for (int i = 0; i <= P; ++i) {
    for (int j = 0; j < S; ++j) {
        int ans, x, y;

        // Min. no. of coins with current coin
        x = (i - denominations[j] >= 0) ? dp[i - denominations[j]][j] + 1: 0;

        // Min. no. of coins w/o current coin
        y = (j > 0) ? dp[i][j - 1] : 0;

        ans = min(x, y);
        if (ans == 0) ans = max(x, y);
        dp[i][j] = ans;
    }
}

ご協力ありがとうございました。

4

1 に答える 1

1

バグは、現在のコインを使用することと使用しないことの両方が禁止されている場合に、ケースを正しく処理していないことです。これは、たとえば、あなたの例で発生します。i = 1およびj = 0の場合、何も使用しないか、4cコインだけを使用して合計1cを作ろうとしています。しかし、これは 4c コインではできませんし、4c コインなしではできません。

このような場合、x と y の両方に 0 が割り当てられ、いずれかif (ans == 0) ans = max(x, y);の可能性が禁止されているケースをキャッチするように設計された行は、誤って ans に 0 を割り当ててしまいます。その結果、外側のループの後の反復では、対応する合計をコインなしで合計することが可能であると「考え」、これに 1 を気軽に追加して、例に対して 1 の間違った答えを与えます。

最もクリーンな修正は、「このアクションは不可能であり、考慮すべきではない」を表すために、0 以外のセンチネル値を選択することだと思います。2 つの可能なアクションを で組み合わせているためmin()、非常に高い値が自然に適合します。

#define INF (INT_MAX-1)   // Or anything higher than the biggest sensible answer

for (int i = 0; i <= P; ++i) {
    for (int j = 0; j < S; ++j) {
        int ans, x, y;

        // Min. no. of coins with current coin
        x = (i - denominations[j] >= 0) ? min(INF, dp[i - denominations[j]][j] + 1) : INF;

        // Min. no. of coins w/o current coin
        y = (j > 0) ? dp[i][j - 1] : INF;

        ans = min(x, y);
        dp[i][j] = ans;
    }
}

x と y の両方が であるため、ans = min(x, y);そうあるべき場合を含め、行がそれ以上の作業をしなくても正しい答えを与えることに注意してください。INFINF

より微妙な点は、計算中にいくつかを読み取ると、その値が許可されることです。これは正当な値であり、タイプ <= のコインの組み合わせではセントを作成できないことを示しています。理想的には、 に選択された値は、任意の正の値を加算または乗算すると、 のままになるという特性を持ちます。これは、このアルゴリズムをさらに調整する必要がないためです。値に対して実行するすべての操作は、正しくそのままになります。で。しかし、整数演算はそのようには機能しないため、値に何かを追加した後、「無限を超えて」いないことを確認し、そうであれば修正する必要があります。これが理由です。dp[a][b]INFabINFINFINFINFINFd[i - denominations[j]][j] + 1呼び出しにラップされmin(INF, ...)ます。(オーバーフローが発生しないように、 -- をINF1 未満と定義したのもこのためです。)INT_MAX

于 2014-08-15T18:24:36.873 に答える