jiwoo2211   11달 전

그리디 알고리즘이 매 순간 최선의 답을 선택해서 문제를 해결하는 알고리즘입니다. 그래서 부분문제의 최적해를 구하는 방법은 아래의 방법대로 하면 될것 같은데

이용 시간이 가장 작은 작업을 m이라고 하자. 이때 다음 작업으로 m을 고르지 않는다고 가정하자. 고른 작업을 m'이라고 하자.

m'을 고른 해는 무조건 m을 고른 해보다 전체 이용시간이 길기 때문에 m을 고를때 부분문제의 최적해는 존재한다.

질문드리고 싶은 것은 이 부분문제에서 얻은 답들이 전체 문제의 답인지 증명하는 것을 모르겠습니다.

Green55   11달 전

전체 문제의 답이라는게 정확히 무엇일까요? "모든 부분문제에서, 가장 작은 작업을 고르는 것이 최적이다" 의 이상으로 증명하고 싶은 명제가 무엇인지 잘 모르겠습니다.

twicedtna   11달 전

induction으로 증명할 수 있을 것 같아요. 말씀해주신 방법은 구글에 "greedy stays ahead" 검색해 보시면 더 자세한 설명들이 많을 겁니다.

jiwoo2211   10달 전

greedy stays ahead검색해서 공부해보고 이해했습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.