가중 구간 스케줄링의 OPT(j) 점화식에서 현재 구간을 선택하지 않는 항을 빼면 왜 최적해를 잃나요?

첫 j개 작업의 최적 스케줄이 항상 j를 포함하는 것은 아니기 때문입니다. j를 선택하는 경우에는 weight[j] + OPT(p(j))를 얻지만, j를 건너뛰는 최적해는 첫 j-1개 안에서 이미 더 큰 보상을 만들 수 있어 OPT(j-1)가 됩니다. 따라서 OPT(j)=max(weight[j]+OPT(p(j)), OPT(j-1))의 두 항이 모두 필요합니다.

앞 작업들의 최적값이 OPT(4)=14이고 작업 5의 weight가 7, p(5)=2, OPT(2)=6이라고 하겠습니다. 작업 5를 넣는 후보는 7+6=13이라 현재 값 14를 넘지 못합니다. 선택 항만 쓰면 13으로 내려가지만, 실제 최적 스케줄 [1,3,4]를 건너뛰게 됩니다. 작업이 짧거나 뒤에 있다는 이유로 마지막 작업을 넣는 것은 가중치가 있는 문제에서 안전하지 않습니다.

두 경우 분할은 최적해를 빠뜨리지도 중복해서 세지도 않습니다. 최적해가 j를 포함하면 j와 호환되는 작업은 p(j) prefix 안에 있어야 하고, 포함하지 않으면 j-1 prefix의 해입니다. 입력 가중치가 음수일 수 있다면 skip 항은 음수 작업을 선택하지 않을 수 있게 하는 역할도 합니다. 반드시 하나를 선택해야 하는 별도 요구가 있으면 초기값과 불가능 상태를 다시 정의합니다.

이항 분할은 finish 순서 prefix에 대해 귀납적으로 적용됩니다. j를 포함하지 않는 최적해는 첫 j-1개만 사용하므로 그 값이 정확히 OPT(j-1)이고, j를 포함하는 해는 호환성 때문에 p(j) 이전으로 잘립니다. 두 집합은 “j를 포함한다/하지 않는다”로 서로 겹치지 않으며 모든 해를 덮습니다. 예제에서 OPT(4)=14, w5+OPT(2)=7+6=13이므로 작업 5를 넣는 선택만 저장하면 이미 계산한 최적값을 1만큼 잃습니다.