욕심 많은 알고리즘과 동전 알고리즘

Question

우선, 내 하드웨어이며, 찾기가 힘들어서 몇 가지 지침을 정말 고맙게 생각합니다.

1,x,x2...xn의 종별은 x>=1 일 때 동전 문제에 대한 욕심 많은 알고리즘이 항상 효과가 있다는 것을 증명해야합니다.

• 우리는 항상 최소 금액의 동전을 선택할 때 항상 최소 동전 개수로 필요한 금액을받습니다.

감사합니다. 이 같이

Answer 1

내가 완전한 해답을 제공하지 않습니다 오히려 당신을 안내하려고합니다 숙제입니다 :

일반적으로 시도하고 문은 마찬가지임을 스스로 증명 유형의 문제 발생으로

우선 처음 몇 개의 자연수. 당신이 그들을 위해 증거를 만들기 위해 사용하는 것을 요약 해보십시오. 이것은 대개 올바른 접근 방식에 대한 지침을 제공합니다.

여기에 induction을 사용합니다.

또 다른 옵션으로 숫자 시스템에서 숫자가 모두 x 인 것을 나타내는 데 도움이 될 수 있습니다. 이것은 진술이 사실 인 이유를 분명히해야합니다.

희망이 도움이됩니다.