2021.06.25
0-1 배낭 문제(0-1 Knapsack Problem)
0-1 배낭 문제(0-1 Knapsack Problem) 조건 물건들의 집합 O = {O₁, O₂, ..., On}이 있을 경우 Wi : i번째 물건 Oi의 무게 Vi : i번째 물건의 가격(Value) 최대 무게를 T까지 견딜 수 있는 가방(배낭)이 1개 주어짐. 물건들을 가방에 담아야 함. 가방에 넣은 물건들의 가격(V) 합이 최대가 되도록 물건 선택 단, 물건들의 무게 합이 T를 넘지 않아야 함. 예 : 무역을 하는 상인이 매출의 일정 비율을 이익으로 가져갈 떄 이익을 극대화하려면 최대한 비싼 물건들을 가지고 다니면서 팔아야 하지만, 사용할 수 있는 운송 수단(또는 배낭)에는 최대 T 무게까지의 물건말 실을 수 있음. 각각의 물건에 대한 무게(W)와 가격(V)은 이미 알고 있음. 물건들을 어떻게 조..
