속성이 하나있을 때, 거기에 무슨 일이 일어나고 있는지 이해합니다. 두 개 이상의 속성이있을 때 배낭 문제를 이해하는 데 문제가 있습니다.추가 속성이있는 배낭 알고리즘
나는 2 개 속성 배낭 알고리즘을 사용하는 프로그램을 작성해야합니다. 교사는 우리에게 말했습니다. 그것은 3d 배열로 이루어져야합니다. 나는 그러한 어레이가 어떻게 생겼는지 상상할 수 없다.
의 여기 가정 해 봅시다 내 입력의 :
4 3 4 // number of records below, 1st property of backpack, 2nd property of backpack
1 1 1 // 1st property, 2nd property, cost
1 2 2 // 1st property, 2nd property, cost
2 3 3 // 1st property, 2nd property, cost
3 4 5 // 1st property, 2nd property, cost
그리고 출력은 같을 것이다 :
4 // the cheapest sum of costs of 2 records
1 3 // numbers of these 2 records
출력 설명 : 기록의 2 개 세트 입력 1'st 라인에의 적합 :
(1) (2)-4
3 4 5
레코드 1 세트 (4 < 5) 가장 저렴한이기 때문에 레코드 번호는, 우리는 그것을 선택했다. 그러한 레코드 집합이 있는지 여부를 알아 내야 할뿐만 아니라 합계 된 레코드를 찾아야합니다.
그러나 지금은 단지 3D 배열이 어떻게 보이는지 이해할 필요가 있습니다. 당신 중 일부는 저의 이미지에서와 같이 레이어로 레이어를 보여 주면서 어떻게 보이게 할 수 있습니까? 감사합니다. .
첫 번째 배열을 잘 모르겠습니다. 배열의 값의 의미는 무엇입니까? – gmlobdell
예. V = 2 및 V = 1 인 1 2 항목이있는 배낭에서 최대 2 배의 V = 1 항목을 넣을 수 있습니다. V = 3이고 항목이 V = 1 및 V = 1 인 배낭에서이 항목을 최대로 둘 수 있으므로 해당 셀 내에 v = 2가됩니다. v = 3 및 항목 1,1,2가있는 배낭에는 최대 2 개의 항목 (v = 1, v = 2)을 넣을 수 있으므로 3을 제공합니다. 셀 안의 값은 배낭의 최대 패키지입니다. – Paulina
교사가 [여러 제약 배낭 문제를 찾습니다] (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) –