n개 항목의 가중치와 값이 주어집니다. 작업은 배낭의 최대 총 값을 얻기 위해 용량 W의 배낭에 다음 무게와 값에 대해 0/1 배낭에 따라 항목을 인쇄하는 것입니다.
0/1 배낭이란 무엇입니까?
배낭은 일정한 크기의 가방이나 일정한 무게를 견딜 수 있는 가방과 같습니다. 배낭에 포함된 각 품목에는 약간의 가치(이익)와 약간의 무게가 있습니다. 배낭이 담을 수 있는 총 무게에 따라 최대 이익을 얻을 수 있는 무게를 추가해야 합니다.
그래서 우리는 무게, 가치(이익), 배낭이 담을 수 있는 가방의 총 무게를 가지고 있습니다. 그래서 0/1 배낭에서는 포함되거나 포함되지 않은 항목에 대해 1과 0만 언급합니다. 여기서 0은 할 수 없는 항목입니다. t는 가방에 추가되지만 1은 배낭에 포함될 수 있는 항목입니다.
간단한 예를 통해 이해합시다 -
Let us assume val[] = {1, 2, 5, 6}//value or profit
wt[] = {2, 3, 4, 5}//weight
W = 8//Capacity 배낭 테이블은 -
배낭.jpg
배낭 표는 다음 공식의 도움으로 채울 수 있습니다 -
K [i ,w] =최대 {K [i−1, w], K [i−1, w−wt [i]] + Val[i]}
역추적 접근 방식을 사용하여 테이블 해결,
이제 우리는 모든 항목의 수익 데이터와 특정 항목을 추가한 후 얻을 수 있는 최대 가중치 내에서 최대 수익을 얻었습니다.
- k[n][w] 형식을 역추적하기 시작합니다. 여기서 k[n][w]는 8입니다.
- 파란색 화살표가 검은색 화살표가 가는 위쪽까지 가는 방향으로 우리는 위쪽으로 갈 것입니다. 따라서 8은 4번째 행에만 있으므로 4번째 개체를 포함합니다. 즉, 4번째 항목을 추가한 후 최대 이익을 얻었다는 의미입니다.
- 총 이익 8에서 4번째 항목을 추가하여 얻은 이익, 즉 6을 뺀 값은 2입니다.
- 최대 이익으로 2를 얻을 때 테이블을 역추적하여 찾습니다. 두 번째 항목을 추가할 때 얻었습니다.
- 그래서 우리는 가방을 효율적으로 채우고 최대의 이익을 얻을 수 있도록 두 번째와 네 번째 항목을 배낭에 추가합니다.
예시
Input: val[] = {60, 100, 120}
wt[] = {10, 20, 30}
w = 50
Output: 220 //max value
30 20 //weights
Explanation: to reach till the maximum weight i.e. 50 we will add two weights value,
30 whose value is 120 and 20 whose value is 100
Input: val[] = {10, 40, 50}
wt[] = {2, 4, 5}
w = 6
Output: 50
4 2
Explanation: to reach till the maximum weight i.e. 6 we will add two weights value, 4
whose value is 40 and 2 whose value is 10. 알고리즘
Start
Step 1-> In function max(int a, int b)
Return (a > b) ? a : b
Step 2-> In function printknapSack(int W, int wt[], int val[], int n)
Decalare i, w, K[n + 1][W + 1]
Loop For i = 0 and i <= n and i++
Loop For w = 0 and w <= W and w++
If i == 0 || w == 0 then,
Set K[i][w] = 0
Else If wt[i - 1] <= w then,
Set K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
Else
Set K[i][w] = K[i - 1][w]
Set res = K[n][W]
Print res
Set w = W
Loop For i = n and i > 0 && res > 0 and i--
If res == K[i - 1][w] then,
Continue
Else {
Print wt[i - 1])
Set res = res - val[i - 1]
Set w = w - wt[i - 1]
Step 3-> In function int main()
Set val[] = { 50, 120, 70 }
Set wt[] = { 10, 20, 30 }
Set W = 50
Set n = sizeof(val) / sizeof(val[0])
Call function printknapSack(W, wt, val, n)
Stop 예시
#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
// Prints the items which are put in a knapsack of capacity W
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] +
K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
// stores the result of Knapsack
int res = K[n][W];
printf("maximum value=%d\n", res);
w = W;
printf("weights included\n");
for (i = n; i > 0 && res > 0; i--) {
if (res == K[i - 1][w])
continue;
else {
printf("%d ", wt[i - 1]);
res = res - val[i - 1];
w = w - wt[i - 1];
}
}
}
// main code
int main() {
int val[] = { 50, 120, 70 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printknapSack(W, wt, val, n);
return 0;
} 출력
maximum value=190 weights included 30 20