Chap4-4. 부분 배낭 문제
배낭 문제란? 배경 = 물건 n개의 집합 S = {1, 2, 3, 4, ..., n}이 있고 물건 무게 W = {W1, W2, W3..., Wn}, 물건을 팔았을 때의 가치(이윤) P = {P1, P2, P3, ..., Pn }가 있다고 하자. 조건 = W은 물건 무게 이므로 Wi > 0이어야 한다. P도 Pi > 0이어야 한다. 자신이 배낭에 물건을 가지고 가서 시장에서 판다고 가정하자 배낭에 넣을 수 있는 무게는 제한되었다. 최대 무게를 M이라고 하자 1 ~ n까지의 Wi * Xi ≤ M 이면서 (x= 물건의 개수) 1 ~ n 까지의 Pi * Xi 를 최대화하는 방향을 찾아야 한다. • n개의 물건이 각각 1개씩 있고, • 각 물건은 무게와 가치를 가지고 있으며, • 배낭이 한정된 무게의 물건들을 담..
