ปัญหาการตัดแท่ง (Rod Cutting Problem)

บทนำ

กำหนดแท่งที่มีความยาว n พร้อมตารางราคาสำหรับแต่ละขนาด ต้องการหาว่าต้องตัดแท่งอย่างไรจึงจะได้ราคาสูงสุดเมื่อขายในตลาด

วิธีการคือการลองตัดที่ตำแหน่งต่างๆ และเปรียบเทียบราคาที่ได้หลังจากการตัด ให้ f(n) เป็นราคาสูงสุดที่เป็นไปได้หลังจากตัดแท่งยาว n สามารถเขียนฟังก์ชันได้ดังนี้:

f(n) := ค่าสูงสุดจาก price[i] + f(n - i - 1) โดยที่ i อยู่ในช่วง 0 ถึง (n - 1)

อินพุตและเอาต์พุต

Input: ราคาของขนาดต่างๆ และความยาวแท่ง (ที่นี่ความยาวคือ 8)

Output: กำไรสูงสุดหลังขายคือ 22

ตัดแท่งเป็นขนาด 2 และ 6 กำไรคือ 5 + 17 = 22

อัลกอริทึม

rodCutting(price, n)
Input: รายการราคา, จำนวนราคาในรายการ
Output: กำไรสูงสุดจากการตัดแท่ง

Begin
    กำหนดอาเรย์ profit ขนาด n + 1
    profit[0] := 0
    for i := 1 to n, do
        maxProfit := -∞
        for j := 0 to i-1, do
            maxProfit := maximum ของ maxProfit และ (price[j] + profit[i-j-1])
        done
        profit[i] := maxProfit
    done
    return maxProfit
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int rodCutting(int price[], int n) {
    // จากราคาและความยาว n หากำไรสูงสุด
    int profit[n+1];
    profit[0] = 0;
    int maxProfit;
    
    for (int i = 1; i <= n; i++) {
        maxProfit = INT_MIN;  // เริ่มต้นที่ -infinity
        for (int j = 0; j < i; j++)
            maxProfit = max(maxProfit, price[j] + profit[i-j-1]);
        profit[i] = maxProfit;
    }
    return maxProfit;
}

int main() {
    int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int rodLength = 8;
    cout << "Maximum Price: " << rodCutting(priceList, rodLength);
}

ผลลัพธ์

Maximum Price: 22