knapsack Problem 썸네일형 리스트형 0-1 Knapsack Problem(배낭 채우기) 문제어떤 도둑이 배낭을 메고 집에 침입, 도둑은 각 물건의 '무게'와 '값어치'를 알고 있다. 훔칠 물건의 총 무게는 배낭의 용량을 초과할 수 없다.배낭에 담을 수 있는 최대 값어치를 구해보자 입력•보석 (item)의 개수: n•보석 집합 S = {item1, item2,…, itemn}•wi = itemi의 무게, pi = itemi의 가치 •W = 배낭에 넣을 수 있는 총 무게 목표 maximize subject to and .여기서 x는 i번째 아이템을 배낭에 넣을 것인지 넣지 않을 것인지에 대한 1, 0 값 출처 링크 : wikipedia.org Brute-force 방법- 모든 가능한 경우를 반복하면서 w를 초과하기 않으면서 총 이 익을 최대로 하는 경우를 찾는다.- 각 물건의 포함/불포함 여부.. 더보기 이전 1 다음
