코인 문제 경우 1. 정해진 금액을 가장 적은 수의 코인(동전)으로 구성하는 문제를 풀 때(단 각 동전 액면은 무한히 사용 가능), 1, 2, 5, 10, 20, 50, 100, 200 cents 로 되어 있는 유로화 코인이나 1, 5, 10, 50, 100, 500으로 된 원화 동전은 가장 큰 액면부터 차례로 채우면 최적해를 구할 수 있다. 두 경우 모두 뒤의 액면 중에는 이전 액면의 배수가 존재하므로 어느 액면이나 그 전단계의 동전을 통해 구할 수 있고, 이런 경우는 가장 큰 코인부터 답에 포함하게 된다면, 더 적은 액면으로 구성한 뒤 더 큰 액면으로 바꾼 결과와 다름이 없어 최적해가 되는 것이다. 예를 들어 1520원을 구성하고 싶으면 500 * 3 + 10 * 2 이렇게 5개 동전이 최적해이다. ..