Info-Tech

동적 프로그래밍에서 지나치게 많이 일을 해서 좀 줄여보자는 취지로 만들어졌음. 미래를 생각하는게 아니라, 현재상황에서 최선을 택하는 기법이다. 활동선택문제와 백팩문제에서 쓰인다. 1.활동선택문제 이문제는 한 강의실에서 여러 수업을 진행한다고 했을 때, 가장 많이 할 수 있는 경우를 선택하는 문제이다. Si는 시작시간, Fi는 종료시간이다. 위 표를 보면 a1, a4와 a1,a2는 동시대에 진행되기 때문에 선택을 할 수 없다. 하지만 a1,a3은 선택이 가능하다. 즉 결과적으로 A1, a3, a6,a8 || A1, a3, a7, a9 이 후보지이다. G18을 a1이후, a8 이전으로 보면 선택 될수 있는 후보는 {a3,a5,a6,a7} 이다. 이중에서도 겹치지 않게 골라보면 {a3,a6} {a3,a7} {..