硬币变化：动态编程

我编写的代码使用动态编程解决了基本的硬币更改问题，并提供了进行更改所需的最少硬币数量。 但是我希望将每个硬币播放部分的数量存储在最小数量中。

我要做的是初始化一个数组count[] ，就像散列一样，只要找到min ，就会增加coin[j]的数量，即count[coin[j]]++ 。 但这并不像我想要的那样工作，因为它每次找到与coin[j]相对应的min都会添加硬币。 因此，数字不是最终答案中硬币的最终计数。

这是代码：

 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]  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]); } 

Answer 1

你必须保留一个额外的两个dinemsional数组来存储每个值和每个硬币面额的硬币计数。

在内循环中指定新的最小值时，将所有硬币计数从i - coin[j]复制到i，然后递增min_count[i][j] 。 然后所需的硬币数量为coin_count[value] 。

Answer 2

正如您已经指出的那样，自下而上的解决方案每次都会添加硬币，不仅在i == value ，如果您想知道当i == value时硬币的数量，它还取决于子硬币的数量-problems，所以我们需要使用二维数组存储以前的计算：

 #include  #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 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]); } 

驱动程序测试上面的function：

 int main() { int coin[COIN_ARRAY_SIZE] = {5,3,2,1}; makeChange(coin, 4, 8); makeChange(coin, 4, 10); };