กำหนดน้ำหนักและค่าของ n รายการ; งานคือการพิมพ์รายการตาม 0/1 เป้สำหรับน้ำหนักและค่าต่อไปนี้ในเป้ความจุ W เพื่อให้ได้มูลค่ารวมสูงสุดในเป้
เป้ 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 เป็นกำไรสูงสุด ได้เมื่อเราเพิ่มรายการที่ 2
- ดังนั้น เราจะเพิ่มรายการที่ 2 และ 4 ลงในเป้เพื่อเติมเต็มกระเป๋าอย่างมีประสิทธิภาพและเพื่อให้ได้กำไรสูงสุด
ตัวอย่าง
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
