✏️ 10/11 ~ 10/13 강의

4.4 부분 배낭 문제

배낭 (Knapsack) 문제

• n개의 물건이 각각 1개씩 있고,
• 각 물건은 무게와 가치를 가지고 있으며,
• 배낭이 한정된 무게의 물건들을 담을 수 있을 때,
• 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제

부분 배낭 (Fractional Knapsack) 문제

• 물건을 부분적으로 담는 것을 허용,
• 그리디 알고리즘으로 해결

0 - 1 배낭 문제

4.7 허프만 압축