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

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

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

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