여기서 배낭은 용기나 가방과 같습니다. 가중치나 이익이 있는 일부 항목을 제공했다고 가정해 보겠습니다. 우리는 총 가치가 최대 이익을 창출하는 방식으로 일부 품목을 배낭에 넣어야 합니다.

예를 들어, 컨테이너의 무게는 20kg입니다. 물품의 무게의 합이 용기의 무게보다 작거나 같아야 하고, 이익이 최대가 되도록 물품을 선택해야 합니다.

배낭 문제에는 두 가지 유형이 있습니다.

• 0/1 배낭 문제
• 분수 배낭 문제

우리는 두 가지 문제를 하나씩 논의할 것입니다. 먼저 0/1 배낭 문제에 대해 알아 보겠습니다.

0/1 배낭 문제란 무엇입니까?

0/1 배낭 문제는 배낭에 품목이 완전히 채워지거나 품목이 전혀 채워지지 않음을 의미합니다. 예를 들어, 무게가 각각 2kg과 3kg인 두 개의 품목이 있습니다. 2kg 품목을 선택하면 2kg 품목에서 1kg 품목을 선택할 수 없습니다(품목은 나눌 수 없음). 2kg 품목을 완전히 골라야 합니다. 이것은 항목을 완전히 선택하거나 해당 항목을 선택하는 0/1 배낭 문제입니다. 0/1 배낭 문제는 동적 프로그래밍으로 해결됩니다.

분수 배낭 문제란 무엇입니까?

분수 배낭 문제는 항목을 나눌 수 있다는 것을 의미합니다. 예를 들어, 3kg의 품목이 있는데 2kg의 품목을 선택하고 1kg의 품목을 남겨둘 수 있습니다. 부분 배낭 문제는 Greedy 접근 방식으로 해결됩니다.

0/1 배낭 문제의 예.

가중치와 이익이 있는 문제를 고려하면 다음과 같습니다.

가중치: {3, 4, 6, 5}

이익: {2, 3, 1, 4}

배낭의 무게는 8kg입니다.

항목 수는 4입니다.

위의 문제는 다음 방법을 사용하여 해결할 수 있습니다.

엑스_나= {1, 0, 0, 1}

= {0, 0, 0, 1}

각도 cli 제거

= {0, 1, 0, 1}

위의 조합은 가능한 조합입니다. 1은 항목이 완전히 선택되었음을 나타내고 0은 항목이 선택되지 않았음을 의미합니다. 항목이 4개이므로 가능한 조합은 다음과 같습니다.

2⁴= 16; 그래서. 위의 문제를 이용하여 만들 수 있는 조합은 16가지이다. 모든 조합이 이루어지면 최대 이익을 제공하는 조합을 선택해야 합니다.

문제를 해결하는 또 다른 접근 방식은 동적 프로그래밍 접근 방식입니다. 동적 프로그래밍 접근 방식에서는 복잡한 문제를 하위 문제로 나눈 다음 하위 문제의 솔루션을 찾고 하위 문제의 솔루션을 사용하여 복잡한 문제의 솔루션을 찾습니다.

동적 프로그래밍 접근 방식을 사용하여 이 문제를 어떻게 해결할 수 있습니까?

첫 번째,

아래와 같이 행렬을 만듭니다.

위 행렬에서 열은 무게, 즉 8을 나타냅니다. 행은 품목의 수익과 무게를 나타냅니다. 여기서는 가중치 8을 직접 취하지 않았으며 문제는 하위 문제, 즉 0, 1, 2, 3, 4, 5, 6, 7, 8로 나뉩니다. 하위 문제의 해는 다음 폴더에 저장됩니다. 셀과 문제에 대한 답은 최종 셀에 저장됩니다. 먼저 가중치를 오름차순으로 쓰고 아래와 같이 가중치에 따라 이익을 얻습니다.

~ 안에_나= {3, 4, 5, 6}

피_나= {2, 3, 4, 1}

첫 번째 행과 첫 번째 열은 w=0에 대한 항목이 없으므로 0이 됩니다.

i=1일 때, W=1

~ 안에₁= 3; 무게가 3인 세트에는 단 하나의 품목만 있으므로 배낭의 용량은 1입니다. 용량 1kg의 배낭에는 3kg의 품목을 채울 수 없으므로 아래와 같이 M[1][1]에 0을 추가합니다. :

i = 1일 때, W = 2

~ 안에₁= 3; 무게가 3인 세트에 품목이 1개뿐이므로 배낭의 용량은 2입니다. 용량 2kg의 배낭에는 3kg의 품목을 채울 수 없으므로 아래와 같이 M[1][2]에 0을 추가합니다. :

i=1일 때, W=3

~ 안에₁= 3; 세트에는 무게가 3인 항목이 하나만 있고 배낭의 무게도 3이므로; 그러므로 우리는 무게가 3인 아이템으로 배낭을 채울 수 있습니다. 아래와 같이 무게 3, 즉 2에 해당하는 이익을 M[1][3]에 넣습니다.

i=1일 때, W=4

_W1= 3; 세트에는 무게가 3인 항목이 하나만 있고 배낭의 무게는 4이므로; 그러므로 우리는 무게가 3인 아이템으로 배낭을 채울 수 있습니다. 아래와 같이 무게 3, 즉 2에 해당하는 이익을 M[1][4]에 넣습니다.

i=1일 때, W=5

_W1= 3; 세트에는 무게가 3인 항목이 하나만 있고 배낭의 무게는 5이므로; 그러므로 우리는 무게가 3인 아이템으로 배낭을 채울 수 있습니다. 아래와 같이 무게 3, 즉 2에 해당하는 이익을 M[1][5]에 넣습니다.

i=1, W=6일 때

_W1= 3; 세트에는 무게가 3인 항목이 하나만 있고 배낭의 무게는 6이므로; 그러므로 우리는 무게가 3인 아이템으로 배낭을 채울 수 있습니다. 아래와 같이 M[1][6]에 무게 3, 즉 2에 해당하는 이익을 넣습니다.

i=1일 때, W=7

_W1= 3; 세트에는 무게가 3인 항목이 하나만 있고 배낭의 무게는 7이므로; 그러므로 우리는 무게가 3인 아이템으로 배낭을 채울 수 있습니다. 아래와 같이 M[1][7]에 무게 3, 즉 2에 해당하는 이익을 넣습니다.

i=1일 때, W=8

_W1= 3; 세트에는 무게가 3인 항목이 하나만 있고 배낭의 무게는 8이므로; 그러므로 우리는 무게가 3인 아이템으로 배낭을 채울 수 있습니다. 아래와 같이 무게 3, 즉 2에 해당하는 이익을 M[1][8]에 넣습니다.

이제 'i'의 값이 증가하여 2가 됩니다.

i=2일 때, W=1

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에는 무게가 4인 항목이 하나만 있고 배낭의 무게는 1이므로 배낭의 무게는 1입니다. 무게가 4인 항목을 배낭에 넣을 수 없으므로 M[2][1에 0을 추가합니다. ] 아래와 같이 표시됩니다.

i=2일 때, W=2

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에는 무게가 4인 항목이 하나만 있고 배낭의 무게는 2이므로 배낭의 무게는 2입니다. 무게가 4인 항목을 배낭에 넣을 수 없으므로 M[2][2에 0을 추가합니다. ] 아래와 같이 표시됩니다.

i=2일 때, W=3

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에 무게가 3과 4인 두 개의 항목이 있고 배낭의 무게는 3이므로 배낭의 무게는 3입니다. 배낭에 무게가 3인 항목을 넣을 수 있으므로 M[2][3]에 2를 추가합니다. 아래와 같이 표시됩니다:

i=2일 때, W=4

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에 무게가 3과 4인 두 개의 품목이 있고 배낭의 무게는 4이므로 무게가 4인 품목보다 무게가 4인 품목의 이익이 더 크기 때문에 배낭에 넣을 수 있습니다. 3이므로 아래와 같이 M[2][4]에 3을 추가합니다.

i = 2일 때, W = 5

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에 무게가 3과 4인 두 개의 품목이 있고 배낭의 무게는 5이므로 배낭에 무게가 4인 품목을 넣을 수 있고 무게에 해당하는 이익은 3이므로 3을 더합니다. M[2][5]는 아래와 같습니다.

i = 2일 때, W = 6

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에는 무게가 3과 4인 두 개의 항목이 있고 배낭의 무게는 6이므로 배낭에 무게가 4인 항목을 넣을 수 있고 무게에 해당하는 이익은 3이므로 3을 더합니다. M[2][6]은 아래와 같습니다.

i = 2일 때, W = 7

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에 무게가 3과 4인 두 개의 품목이 있고 배낭의 무게는 7이므로 배낭에 무게가 4와 3인 품목을 넣을 수 있으며 무게에 해당하는 이익은 2와 3입니다. 따라서 총 이익은 5이므로 아래와 같이 M[2][7]에 5를 더합니다.

i = 2일 때, W = 8

값 2에 해당하는 가중치는 4, 즉 w₂= 4. 세트에 무게가 3과 4인 두 개의 품목이 있고 배낭의 무게는 7이므로 배낭에 무게가 4와 3인 품목을 넣을 수 있으며 무게에 해당하는 이익은 2와 3입니다. 따라서 총 이익은 5이므로 아래와 같이 M[2][7]에 5를 더합니다.

이제 'i'의 값이 증가하여 3이 됩니다.

i = 3일 때, W = 1

c 부울

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 세트에는 무게가 3, 4, 5인 세 가지 항목이 있고 배낭의 무게는 1이므로 배낭에 두 항목을 모두 넣을 수 없으므로 M[3][에 0을 추가합니다. 1] 아래와 같이 표시됩니다.

i = 3일 때, W = 2

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 세트에는 무게가 3, 4, 5인 세 가지 항목이 있고 배낭의 무게는 1이므로 배낭에 두 항목을 모두 넣을 수 없으므로 M[3][에 0을 추가합니다. 2] 아래와 같이 표시됩니다.

i = 3일 때, W = 3

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 무게가 3, 4, 5인 세트에 각각 3개의 아이템이 있고 배낭의 무게는 3이므로, 무게가 3인 아이템을 배낭에 넣을 수 있고 아이템에 해당하는 이익은 2입니다. 따라서 아래와 같이 M[3][3]에 2를 추가합니다.

i = 3일 때, W = 4

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 무게가 3, 4, 5인 세트에 각각 3개의 항목이 있고 배낭의 무게는 4이므로 무게가 3 또는 4인 항목을 유지할 수 있습니다. 가중치 4에 해당하는 이익(3)이 가중치 3에 해당하는 이익보다 크므로 아래와 같이 M[3][4]에 3을 추가합니다.

i = 3일 때, W = 5

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 무게가 3, 4, 5인 세트에 각각 3개의 항목이 있고 배낭의 무게는 5이므로 무게가 3, 4, 5인 항목을 유지할 수 있습니다. 가중치 4에 해당하는 이익(3)은 가중치 3과 5에 해당하는 이익보다 크므로 아래와 같이 M[3][5]에 3을 더합니다.

i=3일 때, W=6

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 무게가 3, 4, 5인 세트에 각각 3개의 항목이 있고 배낭의 무게는 6이므로 무게가 3, 4, 5인 항목을 유지할 수 있습니다. 가중치 4에 해당하는 이익(3)은 가중치 3과 5에 해당하는 이익보다 크므로 아래와 같이 M[3][6]에 3을 추가합니다.

i=3일 때, W=7

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 무게가 3, 4, 5인 세트에 각각 3개의 품목이 있고 배낭의 무게는 7이므로, 이 경우 이익의 합인 무게 3과 4의 품목을 모두 유지할 수 있습니다. (2 + 3), 즉 5와 같으므로 아래와 같이 M[3][7]에 5를 추가합니다.

i = 3일 때, W = 8

값 3에 해당하는 가중치는 5, 즉 w_삼= 5. 무게 3, 4, 5 세트에 각각 3개의 항목이 있고 배낭의 무게는 8이므로, 이 경우 무게 3과 4의 항목을 모두 유지할 수 있습니다. 이익은 (2 + 3), 즉 5와 같으므로 아래와 같이 M[3][8]에 5를 추가합니다.

이제 'i'의 값이 증가하여 4가 됩니다.

i = 4일 때, W = 1

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 각각 3, 4, 5, 6의 무게 집합에 4개의 항목이 있고 배낭의 무게는 1이므로 모든 항목의 무게가 배낭의 무게보다 크므로 우리는 할 수 없습니다. 배낭에 물건을 추가하세요. 따라서 아래와 같이 M[4][1]에 0을 추가합니다.

i = 4일 때, W = 2

피트 데이비슨

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 각각 3, 4, 5, 6의 무게 집합에 4개의 항목이 있고 배낭의 무게는 2이므로 모든 항목의 무게가 배낭의 무게보다 크므로 우리는 할 수 없습니다. 배낭에 물건을 추가하세요. 따라서 아래와 같이 M[4][2]에 0을 추가합니다.

i = 4일 때, W = 3

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 무게가 3, 4, 5, 6인 세트에 각각 4개의 품목이 있고 배낭의 무게는 3이므로, 무게가 3인 품목을 배낭에 넣을 수 있고 그에 해당하는 이익을 얻을 수 있습니다. 가중치 4는 2이므로 아래와 같이 M[4][3]에 2를 추가합니다.

i = 4일 때, W = 4

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 무게가 3, 4, 5, 6인 세트에 각각 4개의 품목이 있고 배낭의 무게는 4이므로, 무게가 4인 품목을 배낭에 넣을 수 있고 그에 해당하는 이익이 발생합니다. 가중치 4는 3이므로 아래와 같이 M[4][4]에 3을 추가합니다.

i = 4일 때, W = 5

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 무게가 3, 4, 5, 6인 세트에 각각 4개의 품목이 있고 배낭의 무게는 5이므로, 무게가 4인 품목을 배낭에 넣을 수 있고 그에 해당하는 이익이 발생합니다. 가중치 4는 3이므로 아래와 같이 M[4][5]에 3을 추가합니다.

i = 4일 때, W = 6

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 무게 3, 4, 5, 6의 집합에 각각 4개의 항목이 있고 배낭의 무게는 6이므로, 이 경우 무게 3, 4 중 하나의 배낭에 항목을 넣을 수 있습니다. , 5 또는 6이지만 이익, 즉 가중치 6에 해당하는 4가 모든 항목 중에서 가장 높습니다. 따라서 아래와 같이 M[4][6]에 4를 추가합니다.

i = 4일 때, W = 7

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 무게 3, 4, 5, 6 세트에 각각 4개의 항목이 있고 배낭의 무게는 7이므로, 여기서 무게 3과 4의 두 항목을 추가하면 최대값이 생성됩니다. 이익, 즉 (2 + 3)은 5이므로 아래와 같이 M[4][7]에 5를 더합니다.

i = 4일 때, W = 8

값 4에 해당하는 가중치는 6, 즉 w₄= 6. 무게 3, 4, 5, 6 세트에 각각 4개의 항목이 있고 배낭의 무게는 8이므로, 여기서 무게 3과 4의 두 항목을 추가하면 최대값이 생성됩니다. 이익, 즉 (2 + 3)은 5이므로 아래와 같이 M[4][8]에 5를 더합니다.

위 표에서 볼 수 있듯이 5는 모든 항목 중 최대 이익입니다. 포인터는 값이 5인 마지막 행과 마지막 열을 가리킵니다. 이제 5개의 값을 이전 행과 비교하겠습니다. 이전 행, 즉 i = 3에 동일한 값 5가 포함되어 있으면 포인터가 위쪽으로 이동합니다. 이전 행에는 값 5가 포함되어 있으므로 아래 표에 표시된 대로 포인터가 위쪽으로 이동됩니다.

다시 한 번 위 행의 값 5를 비교합니다(예: i = 2). 위 행에는 값 5가 포함되어 있으므로 포인터는 아래 표와 같이 다시 위쪽으로 이동합니다.

다시 위 행의 값 5, 즉 i = 1을 비교하겠습니다. 위 행에는 동일한 값이 포함되어 있지 않으므로 행 i=1로 간주하고 행에 해당하는 가중치는 4입니다. 따라서 , 우리는 가중치 4를 선택했고 아래 표시된 가중치 5와 6을 거부했습니다.

x = { 1, 0, 0}

가중치에 해당하는 이익은 3입니다. 따라서 남은 이익은 (5 - 3)이 2입니다. 이제 이 값 2를 i = 2 행과 비교하겠습니다. 행 (i = 1)에는 값 2가 포함되어 있으므로 ; 따라서 포인터는 아래와 같이 위쪽으로 이동했습니다.

다시 우리는 값 2를 위의 행, 즉 i = 1과 비교합니다. 행 i =0에는 값 2가 포함되어 있지 않으므로 행 i = 1이 선택되고 i = 1에 해당하는 가중치는 3이 표시됩니다. 아래에:

엑스 = {1, 1, 0, 0}

가중치에 해당하는 이익은 2입니다. 따라서 남은 이익은 0입니다. 0 값을 위 행과 비교합니다. 위 행에는 0 값이 포함되어 있지만 이 행에 해당하는 이익은 0입니다. 이 문제에서는 이익을 최대화하기 위해 두 개의 가중치, 즉 3과 4가 선택됩니다.