변경 방법 수를 계산하십시오.

Question

동전이 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. 오버플로 문제로 인한 것입니까?

Answer 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, 2000 1000} 목표량);

Answer 2

루프가 거꾸로되어 있습니다. 코인 종파 고리는 내부 고리이어야합니다.

배열 할당도 의미가 없습니다. 현재 동전의 특정 종파가 목표와 다른 변경 값을 합산하는 중입니다.

데이터 구조에는 벡터 벡터가 있어야합니다. 내부 루프를 실행할 때마다 데이터 구조에 새 벡터를 삽입해야합니다. 이 벡터는 관심 값과 같은 합계를 갖는 동전 집합이어야합니다.

Answer 3

모든 가능한 값을 저장하려면 6001x11 크기의 2 차원 배열을 사용해야합니다 (해당 경우). d [0] [0]으로 시작하여 d [6000] [10]까지 반복하여 최종 답을 얻을 수 있습니다.