# 배낭 문제 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 찾기 -
