Cho trước trọng lượng và giá trị của n mục; nhiệm vụ là in các mục theo gói 0/1 cho các trọng lượng và giá trị sau trong một gói có dung lượng W, để nhận được tổng giá trị lớn nhất trong gói.
0/1 Knapsack là gì?
Knapsack giống như một chiếc túi chỉ có một kích thước cố định hoặc một chiếc túi có thể chịu được một lượng trọng lượng nhất định. Mỗi mặt hàng được bao gồm trong một cái ba lô có một số giá trị (lợi nhuận) và một số trọng lượng đối với nó. Chúng tôi phải thêm các trọng lượng đó để chúng tôi có được lợi nhuận tối đa theo tổng trọng lượng mà một chiếc ba lô có thể giữ.
Vì vậy, chúng tôi có trọng lượng, giá trị của chúng (lợi nhuận) và tổng trọng lượng của túi mà một cái ba lô có thể chứa, vì vậy trong 0/1 cái ba lô, chúng tôi chỉ đề cập đến 1 và 0 cho mặt hàng được bao gồm hoặc không, trong đó 0 là cho mặt hàng có thể ' không được thêm vào túi, trong khi số 1 dành cho mặt hàng có thể được cho vào túi.
Hãy hiểu với sự trợ giúp của Ví dụ đơn giản -
Let us assume val[] = {1, 2, 5, 6}//value or profit
wt[] = {2, 3, 4, 5}//weight
W = 8//Capacity Bảng knapsack của nó sẽ là -
knapsack.jpg
Bảng Knapsack có thể được điền với sự trợ giúp của công thức sau -
K [i, w] =max {K [i − 1, w], K [i − 1, w − wt [i]] + Val [i]}
Giải bảng bằng cách sử dụng phương pháp theo dõi ngược,
Giờ đây, chúng tôi có dữ liệu về lợi nhuận của mọi mặt hàng và lợi nhuận tối đa trong phạm vi trọng lượng tối đa mà chúng ta có thể nhận được sau khi thêm các mặt hàng nhất định.
- Bắt đầu biểu mẫu kiểm tra lại k [n] [w], trong đó k [n] [w] là 8.
- Chúng tôi sẽ đi theo hướng đi lên khi mũi tên màu xanh lam hướng dẫn đến tất cả các con đường đi lên nơi các mũi tên màu đen sẽ đi tới. Vì vậy, số 8 chỉ ở hàng thứ 4 nên chúng tôi sẽ bao gồm đối tượng thứ 4, điều này có nghĩa là chúng tôi đã nhận được lợi nhuận tối đa sau khi thêm mục thứ 4.
- Chúng tôi sẽ trừ đi tổng lợi nhuận là 8 với lợi nhuận thu được bằng cách thêm mục thứ 4, tức là 6, chúng tôi sẽ nhận được 2.
- Chúng tôi sẽ duyệt lại bảng để tìm kiếm khi chúng tôi nhận được 2 là lợi nhuận tối đa. Chúng tôi đã hiểu khi thêm mục thứ 2
- Vì vậy, chúng tôi sẽ thêm mặt hàng thứ 2 và thứ 4 trong một chiếc ba lô để làm đầy túi một cách hiệu quả và đạt được lợi nhuận tối đa.
Ví dụ
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. Thuật toán
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 Ví dụ
#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;
} Đầu ra
maximum value=190 weights included 30 20