Bài toán cắt thanh (Rod Cutting)

Giới thiệu

Cho một thanh có độ dài n. Cũng được cung cấp một bảng giá chứa giá cho từng kích thước khác nhau. Mục tiêu là xác định lợi nhuận tối đa bằng cách cắt thanh và bán chúng trên thị trường.

Để có giá tốt nhất, ta thực hiện cắt tại các vị trí khác nhau và so sánh các giá sau khi cắt thanh.

Gọi f(n) là giá trị lớn nhất có thể đạt được sau khi cắt thanh độ dài n. Ta có thể viết hàm f(n) như sau:

f(n) := giá trị tối đa từ price[i] + f(n – i – 1), với i trong khoảng từ 0 đến (n – 1).

Đầu vào và Đầu ra

Đầu vào:

Giá của các độ dài khác nhau và độ dài thanh. Ở đây độ dài là 8.

Đầu ra:

Lợi nhuận tối đa sau khi bán là 22.

Cắt thanh thành độ dài 2 và 6. Lợi nhuận là 5 + 17 = 22

Thuật toán

rodCutting(price, n)
Đầu vào: Danh sách giá, số lượng giá khác nhau trong danh sách.
Đầu ra: Lợi nhuận tối đa bằng cách cắt thanh.

Begin
    định nghĩa mảng profit kích thước n + 1
    profit[0] := 0
    for i := 1 to n, do
        maxProfit := -∞
        for j := 0 to i-1, do
            maxProfit := max(maxProfit, price[j] + profit[i-j-1])
        done
        profit[i] := maxProfit
    done
    return maxProfit
End

Ví dụ (C++)

#include <iostream>
using namespace std;

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

int rodCutting(int price[], int n) {
    // từ giá và độ dài n, tìm lợi nhuận tối đa
    int profit[n+1];
    profit[0] = 0;
    int maxProfit;
    
    for (int i = 1; i <= n; i++) {
        maxProfit = INT_MIN;  // ban đầu đặt là -vô cực
        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);
}

Kết quả

Maximum Price: 22