1

私が書いたコードは、動的計画法を使用して基本的なコインの変更の問題を解決し、変更を行うために必要なコインの最小数を示します。しかし、各コインプレイのカウントを最小数に保存したいと思います。

私がやろうとしているのは、配列count[]を初期化することであり、ハッシュのように、が見つかるcoin[j]たびに の数を増やします。しかし、これは、に対応するものを見つけるたびにコインを追加するため、私が望むようには機能していません。したがって、この数字は、最終回答のコインの最終カウントではありません。mincount[coin[j]]++mincoin[j]

コードは次のとおりです。

void makeChange(int coin[], int n, int value)
{
    int i, j;
    int min_coin[MAX];
    int min;

    int count[MAX];
    min_coin[0] = 0;

    for (i=1; i <= value; i++)
    {
            min = 999;
            for (j = 0; j<n; j++)
            {
                    if (coin[j] <= i)
                    {
                            if (min > min_coin[i-coin[j]]+1)
                            {
                                    min = min_coin[i-coin[j]]+1;
                                    count[coin[j]]++;
                            }
                    }
            }
            min_coin[i] = min;
    }

    printf("minimum coins required %d \n", min_coin[value]);

}
4

2 に答える 2

1

各値と各コインの金種のコイン数を格納するために、追加の 2 次元配列を保持する必要があります。

内側のループで新しい最小値を割り当てるときは、すべてのコイン カウントをi - coin[j]から i にコピーしてから、 をインクリメントしますmin_count[i][j]。必要なコインの数は ですcoin_count[value]。

于 2014-05-09T07:41:08.967 に答える
0

すでに指摘したように、ボトムアップ ソリューションは、 のときだけでなく、のときi == valueのコインの数を知りたい場合はi == value、副問題のコインの数に依存するため、前の値を保存する必要があります。 2 次元配列を使用した計算:

#include <stdio.h>

#define MAX 1000
#define COIN_ARRAY_SIZE 4

void makeChange(int coin[], int n, int value)
{
    int i, j, k;
    int min_coin[MAX];

    int count[MAX + 1][COIN_ARRAY_SIZE] = {0}; // zeroing
    int min;

    //int count[MAX];
    min_coin[0] = 0;

    for (i=1; i <= value; i++)
    {
        min = 999;
        for (j = 0; j<n; j++)
        {
            if (coin[j] <= i)
            {
                if (min > min_coin[i-coin[j]]+1)
                {
                    min = min_coin[i-coin[j]]+1;
                    for(k = 0; k < n; ++k)
                    {
                        count[i][k] = count[i-coin[j]][k]; // copy coin counts when value=i-coin[j]
                    }
                    count[i][j]++; // use a coin[j], increase the count
                }
            }
        }
        min_coin[i] = min;
    }

    printf("minimum coins required %d \n", min_coin[value]);
    for(int i = 0; i < COIN_ARRAY_SIZE; ++i)
        printf("%d: %d\n", coin[i], count[value][i]);

}

上記の機能をテストするドライバー プログラム:

int main()
{
    int coin[COIN_ARRAY_SIZE] = {5,3,2,1};
    makeChange(coin, 4, 8);
    makeChange(coin, 4, 10);
};
于 2014-05-09T09:26:16.320 に答える