어느 공장에서 근무 계획을 세우려고 한다. 아래 표에서 는 작업 를 마쳤을 때 얻을 수 있는 이득이며 는 작업 의 마감 일자(deadline)를 나타낸다. 모든 작업은 마치는데 1일이 걸린다. 작업을 수행할 수 있는 기계가 대가 있다면, 일동안 얻을 수 있는 이익의 최댓값을 구하시오.
| 작업 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| | 40 | 35 | 30 | 29 | 25 | 24 | 20 | 18 | 16 | 16 | 15 | 12 | 10 | 8 | 7 |
| 2 | 2 | 1 | 3 | 2 | 1 | 4 | 2 | 3 | 4 | 3 | 2 | 3 | 2 | 2 |