동전 교환을위한 동적 프로그래밍

Question

주어진 금액 x는 각 동전 ci가 주어진 무게 wi를 갖도록 동전 시스템 C = {c1, c2, ... ck}에서 변경되어야합니다. 가능한 변경 사항의 총 가중치를 계산하고 싶습니다. 동일한 동전을 다른 순서로 포함하면 두 가지 변경 사항이 달라집니다.

위의 문제에 대해 어떻게 동적 프로그래밍 재귀를 할 수 있습니까? 최소 동전 교환 문제 (즉, x> 0에 대해 C (x) = min {C (x-c) +1)에 대한 재귀를 안다. 하지만 내 혼란은 가능한 변화의 총중량입니다. 감사합니다.

Answer 1

순진한 접근 방식 인 "배열에 저장 응답"이 작동합니다. C [i]는 코인 값, W [i]는 코인 중량, N은 코인 수를 나타냅니다.

재귀 부분은 다음과 같습니다

long sum = 0; 
for (int i = 0; i < N; ++i) 
    if (C[i] <= x) 
     sum += W[i] + total_change_weight(x-C[i]); 

샘플 프로그램을 입력, 출력 및 C/W 초기화하지 않고 다음과

#define N 10 
#define MAX_VALUE 101 

long C[N]; 
long W[N]; 
long totals[MAX_VALUE]; 

long total_change_weight(long x) 
{ 
    if (x == 0) 
     return 0; 
    if (totals[x] >= 0) 
     return totals[x]; 

    long sum = 0; 
    for (int i = 0; i < N; ++i) 
     if (C[i] <= x) 
      sum += W[i] + total_change_weight(x-C[i]); 
    totals[x] = sum; 

    return sum; 
} 

void main() 
{ 
    long value = 100; 
    //initialize C 
    ... 
    //initialize W 
    ... 
    //initialize totals 
    for (long i = 0; i < MAX_VALUE; ++i) 
     totals[i] = -1; 
    long result = total_change_weight(value); 
}