โปรแกรม C++ แก้ปัญหา Knapsack 0-1 ด้วย Dynamic Programming

ภาพรวม

โปรแกรม C++ นี้แก้ปัญหา 0-1 Knapsack Problem โดยใช้ Dynamic Programming กำหนดให้มีชิ้นส่วน n ชิ้น แต่ละชิ้นมีน้ำหนัก (weight) และค่า (value) ต้องเลือกชิ้นส่วนใดบ้างเพื่อให้ค่ารวมมากที่สุด โดยน้ำหนักรวมไม่เกินความจุกระเป๋า (W) แต่ละชิ้นเลือกได้สูงสุด 1 ชิ้น (0-1)

อัลกอริธึม Dynamic Programming

1. สร้างตาราง DP ขนาด (n+1) x (W+1) โดย dp[i][w] = ค่าสูงสุดที่ได้จาก i ชิ้นแรก ด้วยความจุ w
2. Base case: dp[0][w] = 0, dp[i][0] = 0
3. Transition:
   • ถ้า weight[i-1] <= w: dp[i][w] = max(value[i-1] + dp[i-1][w-weight[i-1]], dp[i-1][w])
   • ถ้า weight[i-1] > w: dp[i][w] = dp[i-1][w]
4. คำตอบอยู่ที่ dp[n][W]

โค้ดตัวอย่าง

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapSack(int W, const vector& wt, const vector& val, int n) {
    vector> dp(n + 1, vector(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i-1] <= w) {
                dp[i][w] = max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

int main() {
    int n, W;
    cout << "Enter the number of items in a Knapsack: ";
    cin >> n;
    
    vector val(n), wt(n);
    for (int i = 0; i < n; i++) {
        cout << "Enter value and weight for item " << i << ": ";
        cin >> val[i] >> wt[i];
    }
    
    cout << "Enter the capacity of knapsack: ";
    cin >> W;
    
    cout << "\nMaximum value: " << knapSack(W, wt, val, n);
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter the number of items in a Knapsack: 4
Enter value and weight for item 0: 10 50
Enter value and weight for item 1: 20 60
Enter value and weight for item 2: 30 70
Enter value and weight for item 3: 40 90
Enter the capacity of knapsack: 100
Maximum value: 40

การเพิ่มเติม: แสดงรายการที่เลือก

// หลังคำนวณ dp เสร็จ ให้ trace back:
int w = W;
for (int i = n; i > 0 && w > 0; i--) {
    if (dp[i][w] != dp[i-1][w]) {
        cout << "Item " << i-1 << " (value=" << val[i-1] << ", weight=" << wt[i-1] << ") selected\n";
        w -= wt[i-1];
    }
}

ความซับซ้อน

• เวลา: O(nW) - Pseudo-polynomial (ขึ้นอยู่กับค่า W ไม่ใช่แค่ n)
• พื้นที่: O(nW) - สามารถลดเหลือ O(W) ได้โดยใช้ 1D array
• ข้อจำกัด: W ใหญ่เกินไปจะกินหน่วยความจำมาก