동전 변화 만 1 동전

Question

문제의 각 교단의와는 다음과 같습니다

pair<bool, bitmask>[n][A] memo;  
// memo[i][j].first will be true if its possible to 
// use up to i-th denomination for amt j 
// memo[i][j].second will contain info on which 
// denominations are used 
for i = 0 to n: 
    for j = 1 to A: 
    if (i==j): C[i][j] = {true, {i}} 
    else if (C[i-1][j].first == true): C[i][j] = C[i-1][j]] 
    else if (...see recurrance relation...): 
     C[i][j] = {true, C[i-1][j]+{denom[i]}} 
    else: C[i][j] = false 

가 지금까지 정확 :

알고리즘은 내가 좋아하는 무언가가되어 함께했다? 그러나 나는 내 시도가 어떻게 보이는지 내가 수도 증거의 정확성을 ... 잘 모르겠습니다 경우 단지 1의 경우

... 영어로 코드를 재 작성과 같은 : 내가 해결하기 위해 우리는 항상 교단의 한 동전을 사용할 수 있습니다 amt = i. 첫 번째 다른 경우 : 현재 금액을 사용하는 없이 amt에 대한 솔루션이있는 경우 해당 솔루션을 다시 사용할 수 있습니다. 다른 2 들어있는 경우 : 표 크기 nA의이다 : 현재의 명칭을 사용할 수있는 경우 (< = AMT) 및 교단 복잡성에 대한

은 ... 우리가 할 수있는, 사용되지 않습니다. 그리고 각 세포는 O (1) 시간을 채 웁니다. 누군가가 올바른 방향으로 나를 가리킬 수 있습니까?

Answer 1

네, 전적으로 당신이 여기있는 바대로 말이죠. 해결하려는 문제는 본질적으로 부분 집합 합계 문제이며 솔루션은 표준 동적 프로그래밍입니다 (http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution 참조).

정확성 측면에서 재발 관계와 기본 사례를 설명하는 것이 좋을 것이라고 나는 말할 수 있습니다. 양식적인 관점에서, 나는 코드를 검토하고 모든 라인을 정당화하지는 않지만 오히려 큰 그림에 초점을 맞출 것이다. 따라서 테이블이 나타내는 것과 기본 사례와 반복 관계를 설정하는 방법을 설명하면 독자는 코드를 쉽게보고 구현할 수 있습니다.

런타임의 경우 : 예, 알고리즘은 테이블의 요소를 반복하면서 설명을 올바르게 입력합니다.