코인 변경에 대한 변형

Question

일반적인 코인 변경 문제는 x1, x2, ..., xn이라는 무제한 동전을 사용하여 값 v를 변경할 수 있는지 여부를 묻습니다.하지만 궁금합니다 한 번에 각 동전을 사용하여 동일한 문제를 파악하는 방법에 대해 알아보십시오.

원래 접두사의 값을 반복하고 v-x_i를 변경할 수 있는지 여부는 알 수 있지만 교단 당 최대 한 개의 동전으로 제한된 경우 손실이 발생합니다.

나를 시작할 수있는 팁이 있습니까? 나는 교단의 접두어를 반복 할 수 있다고 생각할 수도 있습니다. 잘 모르겠지만 ...

Answer 1

동전 교환 문제로, 앞으로 또는 뒤로 재발을 사용할 수 있습니다. ur 문에서는 u가 뒤로 사용되었습니다. 여기에 앞으로의 방법을 알려 드리겠습니다. 그리고 무제한 버전과 AT-MOST-ONCE 버전을 쉽게 해결할 수 있습니다.

f가 1D 부울 배열이라고 가정합니다. f [i]는 u가 값 i에 대해 변경을 할 수 있는지 여부를 나타냅니다. 처음에는 f [0] = true이고, 다른 것은 false와 같습니다.

UNLIMITED 버전 :

for (int i=1;i<=n;i++) 
    for (int j=0;j<v;j++) 
     if (f[j]) 
      f[j+x[i]]=true; 

AT-MOST-ONCE 버전 :

for (int i=1;i<=n;i++) 
    for (int j=v-1;j>=0;j--) 
     if (f[j]) 
      f[j+x[i]]=true; 

유일한 차이는 루프 J위한 순서이다.

u를 이해하는 데 도움이 예 :

비용 경화의 한 종류가 가정 2. 즉 X [1] = 2. 제 1 알고리즘 이후에, v = 1

일 때, u는 f [0] = f [2] = f [4] = f [6] = f [8] = f [10] = 참을 얻을 수있다.

그러나 두 번째 알고리즘의 경우 u는 f [0] = f [2] = true 만 얻을 수 있습니다.