배낭훔치기 알고리즘 S = {item1,item2 ... } Wi = item의 무게 Pi = item의 가치 W = 배낭에 넣을 수 있는 최대 무게 무게가 넘지 않으면서 가치가 최대가 되도록 A를 결정 Brute force 알고리즘 n개의 물건에 대해서 모든 부분 집합을 다 고려함 크기가 n인 집합의 부분집합 수는 2^n개... Greedy Approach 0-1 The Knapsack Problem 1 가장 비싼 물건부터 우선적으로 채운다 최적 알고리즘은 아니다! => 값어치를 기준으로 했을 때 최