โปรแกรมหากำไรสูงสุดจากการตัดแท่งไม้ใน C++ (Rod Cutting Problem)

ภาพรวมปัญหา

ให้แท่งไม้ยาว n และราคาของแต่ละความยาว (price[i] = ราคาความยาว i+1) ต้องการหากำไรสูงสุดจากการตัดแท่งไม้ขาย

ตัวอย่าง

Input: prices = [1, 5, 8, 9, 10, 17, 17, 20], n = 8

Output: 22

คำอธิบาย: ตัดเป็น 2 + 6 → ราคา 5 + 17 = 22

แนวทางแก้ปัญหา (Dynamic Programming)

นี่คือปัญหา Rod Cutting Problem Classic DP

1. dp[i] = กำไรสูงสุดสำหรับแท่งยาว i
2. dp[0] = 0
3. สำหรับ i = 1 ถึง n: dp[i] = max_{1≤j≤i} (price[j-1] + dp[i-j])
4. คำตอบ = dp[n]

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

#include <bits/stdc++.h>
using namespace std;

int rodCutting(int price[], int n) {
    vector dp(n + 1, 0);
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        int maxProfit = INT_MIN;
        for (int j = 0; j < i; j++) {
            maxProfit = max(maxProfit, price[j] + dp[i - j - 1]);
        }
        dp[i] = maxProfit;
    }
    return dp[n];
}

int main() {
    int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int rodLength = 8;
    cout << rodCutting(priceList, rodLength);
    return 0;
}

ผลลัพธ์

22

การสร้างคำตอบ (Reconstruct Solution)

เพื่อทราบว่าตัดอย่างไร ให้เก็บการเลือกที่ดีที่สุด:

vector rodCutting_solution(int price[], int n) {
    vector dp(n + 1, 0), cuts(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int maxProfit = INT_MIN;
        for (int j = 0; j < i; j++) {
            if (price[j] + dp[i - j - 1] > maxProfit) {
                maxProfit = price[j] + dp[i - j - 1];
                cuts[i] = j + 1; // ความยาวที่ตัดครั้งแรก
            }
        }
        dp[i] = maxProfit;
    }
    
    vector result;
    while (n > 0) {
        result.push_back(cuts[n]);
        n -= cuts[n];
    }
    return result; // ความยาวชิ้นที่ตัด
}

ความซับซ้อน

• เวลา: O(N²)
• พื้นที่: O(N)

ความสัมพันธ์กับ Unbounded Knapsack

Rod Cutting = Unbounded Knapsack โดย weight = length, value = price, capacity = n

แตกต่าง: Knapsack ปกติแต่ละ item ใช้ได้ 1 ครั้ง (0/1) แต่ Rod Cutting ใช้ความยาวเดิมได้หลายครั้ง (Unbounded)