[작성중][18-알고리즘]배낭 문제(Knapsack Problem)
2018.06.18
배낭 문제(Knapsack Problem)라는 것은 예를 들어서 도둑이 한 밤중에 어느 가정집에 들어갔다. 그 집에는 금고가 있었다. 도둑은 금고를 여는데 성공을 했다. 금고에는 금, 은, 동, 구리가 있다.(놀랍게도 현금은 없었다.) 도둑의 가방에는 20kg만 담을 수 있다. 그렇다면 도둑은 무엇을 얼마나 담아야지 가방에 담은 물건이 최대의 가치가 들어갈까?의 문제이다. 즉 무엇을 얼마만큼 담아야 가방의 무게가 최대일까?이다. 배낭 문제(Knapsack Problem)는 두 가지로 나누어 진다. 금고에 금 4kg, 은 17kg, 동 10kg이 있다고 하자.(가치는 금>은>동 순이다.) 만약 금, 은, 동을 자를 수 있다고 하면 금 4kg, 은 16kg을 가방에 답는 것이 가방에 최대의 값어치의 물건을 ..