1

私はコイン1、2、4、10、20、40、100、200、400、1000、2000セントのセットを持っています。特定の金額（<= 6000）を支払う方法がいくつあるか知りたいです。C ++での私の現在の解決策は、動的計画法を使用することです。

long long d[6010];
int coin[] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};
d[0] = 1;
for (int i = 0; i < 11; i++) {  // iterate through all coins
    for (int j = 1; j <= 6000; j++)
        d[j] += d[j - coin[i]];
printf("%lld\n", d[20]);

しかし、私の出力は正しくありません：-956301262。オーバーフローの問題が原因ですか？

4

3 に答える 3

2

すべての可能な値を格納するには、サイズ 6001x11 (この場合) の 2 次元配列を使用する必要があります。d[0][0] から開始し、最終的な回答が含まれる d[6000][10] まで繰り返します。

于 2013-03-06T09:16:39.520 に答える
1

あなたのアルゴリズムがどのように機能するかわかりません。私は各宗派をより高いものからより低いものへと再帰的に調べていたでしょう（異なる量をループします）。ルックアップテーブルを使用している間、おそらくあなたのdに似ています。

次のようなもの：

howmanyways(sorted_denominations_set_starting_with_1, target amount):
if this is already in the lookup table return the result
else if sorted_denominations_set_starting_with_1 is {1}, then return target amount
else loop over 0 to target amount/last_set_element
   return the sum of results for howmanyways(sorted_denominations_set_starting_with_1 without the largest element, target amount-last_set_element*loop_index)
keep whatever you return in the lookup table

そしてhowmanyways（{1、2、4、10、20、40、100、200、400、1000、2000}、目標額）;を返します。

于 2013-03-06T07:10:17.453 に答える
1

あなたのループは逆です。コイン単位のループは、内側のループにする必要があります。

配列の割り当ても意味がありません。現在、特定の硬貨単位で目標とは異なる変化の値を合計しているだけです。

おそらく、データ構造としてベクトルのベクトルが必要です。内部ループを実行するたびに、新しいベクトルをデータ構造に挿入する必要があります。このベクトルは、対象の値に等しい合計を持つコインのセットである必要があります。

于 2013-03-06T07:41:49.543 に答える