동전 변경 : 동적 프로그래밍

Question

필자가 작성한 코드는 동적 프로그래밍을 사용하여 기본 동전 변경 문제를 해결하고 변경하는 데 필요한 최소 동전 수를 제공합니다. 그러나 각 코인 플레이 부분의 수를 최소 숫자로 저장하고 싶습니다. 내가 뭘하려고 오전

배열 count[]를 초기화하고, 단지 해시처럼은 min이 발견 될 때마다 coin[j]의 수, 즉 count[coin[j]]++을 증가시킨다. 그러나 이 coin[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]); 

} 

Answer 1

당신은 각각의 값과 각 동전 교단의 동전 수를 저장하는 여분의 2 dinemsional 배열을 유지해야합니다.

내부 루프에 새로운 최소값을 지정할 때 i - coin[j]에서 모든 동전 수를 i로 복사 한 다음 min_count[i][j]을 증가 시키십시오. 필요한 동전의 수는 coin_count[value]입니다.

Answer 2

앞서 언급했듯이 상향식 솔루션은 매번 i == value 일 때뿐만 아니라 동전을 추가하지만, i == value 일 때 동전 수를 알고 싶으면 하위 문제의 동전 수에 따라 달라집니다

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

: 상기 시험하는 기능

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

} 

드라이버 프로그램 : 우리는 2-D 어레이 이전의 계산을 저장할 필요