이론: 배낭 문제와 탐욕 알고리즘

[fineman999]

배낭 문제

1. 분할 가능한 배낭일 경우: 탐욕 알고리즘(Greedy)

• 탐욕적인 전략: 가장 값어치가 높은 아이템을 먼저 채우는 것
• 1kg당 가격을 기준으로 내림차순으로 정렬
• 배낭의 무게(=30kg)를 초과하지 않을 때까지 비싼 순으로 채우기

• Fractional Knapsack Problem: 아이템을 쪼갤 수 있을 경우
• 탐욕 알고리즘은 최적해를 보장하는가?
• 아이템의 분할이 가능하면 Greedy가 최적해를 찾아줌

0-1 배낭 문제( 0-1 Knapsack Problem) #85

• 분할이 불가능한 0-1 배낭 문제는 최적화 문제이며 탐욕 알고리즘은 최적해를 보장하니 않는다.
• 동적계획법 or 백트래킹 or 분기한정법

동적계획법

• n개의 아이템 집합: S
• 아이템의 무게: w
• 아이템의 가치: p
• 배낭의 용량: W
• 배낭의 용량을 넘지 않으면서 가치가 최대가 되는 S의 부분집합 A 찾기