0-1 배낭문제

0-1 배낭문제

• 가성비 순서대로 정렬하고

• 경우를 트리로 표현
• 넣을 경우 뺄 경우 선택해서 리프 노드를 확인

• 0-1 배낭문제는 <= fractional 배낭문제를 응용하여 예측할 수 있으며
• 왼쪽에서 21이란 값을 구했으므로, 오른쪽을 그리디로 예측해보고
• 0-1 배낭은 fractional배낭을 못 넘으므로 21보다 작은 값이 나오면 탐색 안한다

• P(v)+P(i)+fractional(i+1,k-S(v)-S(i))
  • k는 전체 용량, S(v)는 v를 선택 했을 때 용량, S(i)는 다음 i번째 선택했을 시
    P(v)는 v의 이익
• 나올 수 있는 최대 이익이 된다
  • 이 값을 현재까지 구한 최대 이익(MP)과 비교 한다