[작성중][18-알고리즘]배낭 문제(Knapsack Problem)

배낭 문제(Knapsack Problem)라는 것은 예를 들어서 도둑이 한 밤중에 어느 가정집에 들어갔다. 그 집에는 금고가 있었다. 도둑은 금고를 여는데 성공을 했다. 금고에는 금, 은, 동, 구리가 있다.(놀랍게도 현금은 없었다.) 도둑의 가방에는 20kg만 담을 수 있다. 그렇다면 도둑은 무엇을 얼마나 담아야지 가방에 담은 물건이 최대의 가치가 들어갈까?의 문제이다. 즉 무엇을 얼마만큼 담아야 가방의 무게가 최대일까?이다. 

배낭 문제(Knapsack Problem)는 두 가지로 나누어 진다. 금고에 금 4kg, 은 17kg, 동 10kg이 있다고 하자.(가치는 금>은>동 순이다.) 만약 금, 은, 동을 자를 수 있다고 하면 금 4kg, 은 16kg을 가방에 답는 것이 가방에 최대의 값어치의 물건을 담는 것이다. 그런데 금, 은, 동을 자를 수 없다면 금 4kg, 동 10kg만 넣는 것이 최선의 선택일 것이다.(아쉽게도 은은 담을 수 없다.) 이렇게 담을 수 있는 물건을 자를 수 있는가? 없는가에 따라서 2가지 문제 형태가 생긴다. 

[1] 0-1 Knapsack problem : 가방에 담는 물건을 자를 수 없다. 이 때는 단위 무계당 가치를 비교해서 높은 순으로 가방에 담으면 된다.  

[2] Fractional Knapsack problem :  가방에 담는 물건을 자를 수 있다. 이 때는 넣으려는 물건을

[1] 부르트포스 접근 (Brute force approach)

[2]

[3] 다이나믹 프로그래밍 (Dynamic programming)

[4] 분기 한정법 (Branch and Bound)