Greedy Method
Tue Nov 27 15:20:48 UTC 2007
Tue Nov 27 15:20:48 UTC 2007
greedy-method.py
임의의 동전 셋 coin_set = { 1, 5, 10 } 에서 12를 만들기 위한 가장 적은 동전수는?
3
임의의 동전 셋 coin_set = { 1, 6, 10 } 에서 12를 만들기 위한 가장 적은 동전수는?
3
이와 같이 욕심쟁이 방법을 취할 경우 2번째의 2개라는 더 적은 해가 있음에도 불구하고 10을 선택하는 문제점이 있다
하지만, 구현은 아주 간단하다 단, 아래에서와 같이 coin_set 이 항상 역으로 sort 되어 있어야만 한다
1 #!/usr/bi
psyOblade