ได้รับ Weights และ Values ของ n Items งานคือพิมพ์ Items ตาม 0/1 Knapsack สำหรับ Weights และ Values ที่กำหนด ใน Knapsack ความจุ W เพื่อให้ได้ Maximum Total Value
0/1 Knapsack คืออะไร?
Knapsack คือกระเป๋าที่มีขนาดคงที่ หรือรับน้ำหนักได้จำกัด แต่ละ Item ที่ใส่ใน Knapsack มี Value (Profit) และ Weight เราต้องเลือก Items ที่ให้ Profit สูงสุดภายในน้ำหนักที่ Knapsack รองรับได้
ใน 0/1 Knapsack เราใส่ 1 และ 0 ให้ Item ที่เลือกหรือไม่เลือก โดย 0 = ไม่ใส่ได้, 1 = ใส่ได้
ตัวอย่างง่าย:
val[] = {1, 2, 5, 6} // Value/Profit
wt[] = {2, 3, 4, 5} // Weight
W = 8 // Capacity
ตาราง Knapsack สามารถเติมได้ด้วยสูตร:
K[i, w] = max{K[i-1, w], K[i-1, w-wt[i]] + Val[i]}
แก้ตารางด้วย Backtracking:
- เริ่ม Backtrack จาก K[n][w] ซึ่งคือ 8
- ขึ้นไปด้านบน ตามลูกศรสีน้ำเงิน 8 อยู่ Row 4 เท่านั้น ดังนั้น Include Object 4 (ได้ Max Profit หลังใส่ Item 4)
- ลบ Profit รวม 8 ลบ Profit ของ Item 4 คือ 6 เหลือ 2
- Backtrack หาเมื่อไหร่ได้ Profit 2 ได้ตอนใส่ Item 2
- ดังนั้น ใส่ Item 2 และ 4 ลง Knapsack เพื่อเติมให้เต็มและ Profit สูงสุด
ตัวอย่าง
Input: val[] = {60, 100, 120} wt[] = {10, 20, 30} w = 50
Output: 220 //max value
30 20 //weights
คำอธิบาย: เพื่อให้น้ำหนัก 50 ใส่ Weight 30 (Value 120) และ Weight 20 (Value 100)
Input: val[] = {10, 40, 50} wt[] = {2, 4, 5} w = 6
Output: 50
4 2
คำอธิบาย: น้ำหนัก 6 ใส่ Weight 4 (Value 40) และ Weight 2 (Value 10)
อัลกอริทึม
Start
Step 1: Function max(int a, int b)
Return (a > b) ? a : b
Step 2: Function printknapSack(int W, int wt[], int val[], int n)
Declare i, w, K[n+1][W+1]
Loop For i = 0 to n
Loop For w = 0 to W
If i==0 or 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]
End
End
Set res = K[n][W]
Print res
Set w = W
Loop For i = n down to 1 while res > 0
If res == K[i-1][w]: Continue
Else:
Print wt[i-1]
res = res - val[i-1]
w = w - wt[i-1]
Step 3: Main
Set val[] = {50, 120, 70}
Set wt[] = {10, 20, 30}
Set W = 50
Set n = sizeof(val)/sizeof(val[0])
Call printknapSack(W, wt, val, n)
Stop
ตัวอย่างโค้ด
#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
void printknapSack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];
// Build table K[][] bottom-up
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 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];
}
}
}
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
