Bài toán cắt que tính (Rod Cutting Problem)

Giới thiệu bài toán Rod Cutting Problem

Bài toán Rod Cutting Problem là một bài toán tối ưu hóa trong khoa học máy tính và quản lý sản xuất. Bài toán yêu cầu chúng ta cắt một que tính có độ dài n thành các mảnh có độ dài khác nhau để đạt được giá trị lợi nhuận lớn nhất. Mỗi độ dài của que tính và giá trị lợi nhuận tương ứng với việc cắt que tính thành các mảnh có độ dài đó đã được xác định trước.

Bài toán này có rất nhiều ứng dụng thực tế, ví dụ như trong ngành sản xuất giấy, nơi que tính được sử dụng để sản xuất các sản phẩm giấy khác nhau. Khi đó, việc tối ưu hóa cách cắt que tính có thể giúp tối đa hóa lợi nhuận của doanh nghiệp.

Cách tiếp cận phổ biến nhất để giải quyết bài toán Rod Cutting Problem là sử dụng phương pháp đệ quy hoặc các giải thuật tương tự. Tuy nhiên, với những trường hợp cắt que tính có kích thước lớn, các phương pháp này có thể trở nên không hiệu quả và đòi hỏi nhiều thời gian tính toán. Vì vậy, các phương pháp tối ưu hóa khác như lập trình động cũng được sử dụng để giải quyết bài toán Rod Cutting Problem.

Thuật toán Dynamic Programming

def rod_cutting(lengths, prices, n):
    if n == 0:
        return 0
    max_profit = -1
    for i in range(n):
        max_profit = max(max_profit, prices[i] + rod_cutting(lengths, prices, n - i - 1))
    return max_profit

# Example usage
lengths = [1, 2, 3, 4, 5, 6, 7, 8]
prices = [1, 5, 8, 9, 10, 17, 17, 20]
n = len(lengths)
max_profit = rod_cutting(lengths, prices, n)
print("Maximum profit:", max_profit)

Ở đây, chúng ta đầu tiên định nghĩa một hàm rod_cutting để tính toán giá trị lợi nhuận tối đa mà chúng ta có thể đạt được bằng cách cắt que tính có độ dài n. Tham số lengths và prices lần lượt là danh sách các độ dài và giá trị của các que tính.

Trong hàm rod_cutting, chúng ta sử dụng phương pháp đệ quy để tìm ra giá trị lợi nhuận tối đa mà chúng ta có thể đạt được bằng cách cắt que tính có độ dài n. Với mỗi độ dài que tính i từ 0 đến n-1, chúng ta tính giá trị lợi nhuận của cách cắt que tính thành một mảnh có độ dài i+1 và một mảnh có độ dài n-i-1, và chọn cách cắt nào đem lại giá trị lợi nhuận cao nhất.

Sau đó, chúng ta áp dụng hàm rod_cutting để tính toán giá trị lợi nhuận tối đa mà chúng ta có thể đạt được bằng cách cắt que tính có độ dài từ 1 đến 8. Kết quả được in ra màn hình bằng lệnh print.

Cài đặt thuật toán với C++

Dưới đây là một ví dụ về cài đặt bài toán Rod Cutting Problem bằng C++ sử dụng phương pháp đệ quy:

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

int rodCutting(int n, vector<int> lengths, vector<int> profits) {
    if (n == 0) {  // trường hợp cơ sở
        return 0;
    }
    int maxProfit = 0;
    for (int i = 0; i < n; i++) {
        if (lengths[i] <= n) {
            int profit = profits[i] + rodCutting(n - lengths[i], lengths, profits);
            maxProfit = max(maxProfit, profit);
        }
    }
    return maxProfit;
}

int main() {
    vector<int> lengths = {1, 2, 3, 4, 5, 6, 7, 8};  // độ dài các mảnh que tính
    vector<int> profits = {1, 5, 8, 9, 10, 17, 17, 20};  // giá trị lợi nhuận tương ứng
    int n = 4;  // độ dài của que tính
    int maxProfit = rodCutting(n, lengths, profits);
    cout << "Lợi nhuận lớn nhất có thể đạt được: " << maxProfit << endl;
    return 0;
}

Trong ví dụ này, chúng ta định nghĩa một hàm rodCutting() để tìm lợi nhuận lớn nhất có thể đạt được khi cắt que tính có độ dài n thành các mảnh có độ dài khác nhau. Để làm điều này, chúng ta sử dụng phương pháp đệ quy bằng cách tìm kiếm tất cả các cách cắt que tính và tính toán lợi nhuận của từng cách cắt. Hàm max() được sử dụng để tìm lợi nhuận lớn nhất trong số tất cả các cách cắt.

Đoạn mã trong hàm main() sử dụng một ví dụ cụ thể để kiểm tra hàm rodCutting(). Ở đây, chúng ta đang xem xét que tính có độ dài 4 và các độ dài và giá trị lợi nhuận tương ứng với cách cắt que tính đã được xác định trước. Kết quả trả về là lợi nhuận lớn nhất có thể đạt được.

Bài toán Rod Cutting Problem là một bài toán tối ưu hóa quan trọng trong lĩnh vực khoa học máy tính và toán học ứng dụng. Nó có thể được giải quyết bằng nhiều phương pháp khác nhau, bao gồm cả phương pháp đệ quy, động programming, và giải thuật tìm kiếm nhị phân.

Bài toán này có nhiều ứng dụng thực tiễn trong lĩnh vực sản xuất và kinh doanh, nơi việc tối ưu hóa việc sử dụng tài nguyên là rất quan trọng. Ví dụ, bài toán có thể được áp dụng để tối ưu hóa việc cắt tấm ván hoặc que tính để sản xuất các sản phẩm như nội thất hoặc đồ chơi.

Tuy nhiên, như đã đề cập, phương pháp đệ quy có thể gây ra hiệu suất chậm khi kích thước của bài toán lớn. Vì vậy, trong các ứng dụng thực tế, các phương pháp tối ưu khác như động programming hoặc tìm kiếm nhị phân thường được sử dụng để giải quyết bài toán này.

Cài đặt phương pháp động programming với Python

Để giải quyết bài toán Rod Cutting Problem bằng phương pháp động programming trong Python, ta cũng sử dụng một mảng 1 chiều để lưu trữ kết quả của các bài toán con.

Đầu tiên, ta khởi tạo mảng dp có độ dài n+1 và giá trị ban đầu là 0. Với mỗi chiều dài i từ 1 đến n, ta duyệt qua các chiều dài j từ 1 đến i và tính giá trị lớn nhất có thể đạt được với que tính có chiều dài i bằng cách cắt thành 2 phần: phần đầu tiên có chiều dài j và phần còn lại có chiều dài i-j. Giá trị này được tính bằng công thức dp[i] = max(dp[i], price[j] + dp[i-j]), trong đó price[j] là giá trị của đoạn que tính có chiều dài j.

Cuối cùng, giá trị lớn nhất tìm được là dp[n].

Dưới đây là đoạn mã Python minh họa cho phương pháp động programming này:

def rod_cutting(n, price):
    dp = [0] * (n+1) # Khởi tạo mảng lưu trữ kết quả
    for i in range(1, n+1):
        for j in range(1, i+1):
            dp[i] = max(dp[i], price[j] + dp[i-j]) # Tính giá trị lớn nhất có thể đạt được với chiều dài i
    return dp[n] # Trả về giá trị lớn nhất tìm được

# Ví dụ
n = 8
price = [0, 1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting(n, price)) # In ra giá trị lớn nhất có thể đạt được

Cài đặt phương pháp động programming với C++

Để giải quyết bài toán Rod Cutting Problem bằng phương pháp động programming, ta cần tạo ra một bảng lưu trữ kết quả của các bài toán con. Với mỗi chiều dài que tính từ 0 đến n, ta tính giá trị lớn nhất có thể đạt được bằng cách cắt que tính thành các đoạn có chiều dài khác nhau. Kết quả của bài toán chính là giá trị lớn nhất tìm được.

Để tạo bảng lưu trữ kết quả, ta sử dụng một mảng 1 chiều có độ dài n+1, gọi là dp. dp[i] sẽ lưu trữ giá trị lớn nhất có thể đạt được với que tính có chiều dài i.

Cách tính giá trị cho dp[i] như sau:

• Ban đầu, ta đặt dp[0] = 0, tức là không có đoạn nào được cắt ra từ que tính có chiều dài 0.
• Với mỗi chiều dài j từ 1 đến i, ta tính giá trị lớn nhất có thể đạt được bằng cách cắt que tính thành 2 phần: phần đầu tiên có chiều dài j và phần còn lại có chiều dài i-j. Giá trị này được tính bằng công thức: dp[i] = max(dp[i], price[j] + dp[i-j]), trong đó price[j] là giá trị của đoạn que tính có chiều dài j.

Cuối cùng, giá trị lớn nhất tìm được là dp[n].

Dưới đây là đoạn mã C++ minh họa cho phương pháp động programming này:

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

int rodCutting(int n, vector<int>& price) {
    vector<int> dp(n+1, 0); // Khởi tạo mảng lưu trữ kết quả
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i], price[j] + dp[i-j]); // Tính giá trị lớn nhất có thể đạt được với chiều dài i
        }
    }
    return dp[n]; // Trả về giá trị lớn nhất tìm được
}

int main() {
    int n = 8;
    vector<int> price = {0, 1, 5, 8, 9, 10, 17, 17, 20};
    cout << rodCutting(n, price) << endl; // In ra giá trị lớn nhất có thể đạt được
    return 0;
}

Cài đặt Thuật toán tìm kiếm nhị phân với Python

prices = [0, 2, 5, 7, 8, 10, 13, 17, 18, 22, 25]

def binary_search(prices, n):
    start, end = 1, n
    while start <= end:
        mid = (start + end) // 2
        if prices[mid] <= prices[n - mid]:
            start = mid + 1
        else:
            end = mid - 1
    return prices[end]

def rod_cutting(n):
    if n <= 0:
        return 0
    if n <= len(prices) - 1:
        return prices[n]
    max_price = 0
    for i in range(1, n + 1):
        max_price = max(max_price, binary_search(prices, i) + rod_cutting(n - i))
    return max_price

# Test với đoạn gỗ có độ dài 8
print(rod_cutting(8))  # Kết quả: 22

Trong đoạn code trên, ta sử dụng hàm binary_search để tìm giá trị lớn nhất có thể đạt được khi cắt đoạn gỗ ở vị trí i. Sau đó, ta sử dụng đệ quy để tìm giá trị lớn nhất có thể đạt được khi cắt que tính có độ dài n bằng cách tính giá trị lớn nhất có thể đạt được khi cắt đoạn gỗ ở mỗi vị trí i và cắt que tính còn lại bằng cách gọi đệ quy với đoạn gỗ có độ dài n – i. Cuối cùng, ta trả về giá trị lớn nhất có thể đạt được.

Cài đặt thuật toán tìm kiếm nhị phân với C++

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

int prices[] = {0, 2, 5, 7, 8, 10, 13, 17, 18, 22, 25};

int binary_search(int n) {
    int start = 1, end = n;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (prices[mid] <= prices[n - mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return prices[end];
}

int rod_cutting(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n <= sizeof(prices)/sizeof(prices[0]) - 1) {
        return prices[n];
    }
    int max_price = 0;
    for (int i = 1; i <= n; i++) {
        max_price = max(max_price, binary_search(i) + rod_cutting(n - i));
    }
    return max_price;
}

int main() {
    int n = 8;
    cout << rod_cutting(n) << endl; // Kết quả: 22
    return 0;
}

Trong code trên, hàm binary_search được sử dụng để tìm giá trị lớn nhất có thể đạt được khi cắt que tính ở vị trí i. Hàm rod_cutting tính toán giá trị lớn nhất có thể đạt được khi cắt que tính có độ dài n bằng cách tính giá trị lớn nhất có thể đạt được khi cắt que tính ở mỗi vị trí i và cắt que tính còn lại bằng cách gọi đệ quy với đoạn gỗ có độ dài n – i. Cuối cùng, ta trả về giá trị lớn nhất có thể đạt được.

Đánh giá độ phức tạp của ba thuật toán

1. Phương pháp đệ quy:
   • Độ phức tạp thời gian: O(2^n), với n là độ dài của que tính.
   • Độ phức tạp không gian: O(n), với n là độ dài của que tính.
   • Phương pháp đệ quy có thể gây ra hiệu suất chậm khi kích thước của bài toán lớn.
2. Động Programming:
   • Độ phức tạp thời gian: O(n^2), với n là độ dài của que tính.
   • Độ phức tạp không gian: O(n), với n là độ dài của que tính.
   • Động programming cho phép lưu trữ các giá trị con trước đó để tránh tính toán lại các giá trị đã tính toán trước đó, giúp cải thiện hiệu suất của thuật toán.
3. Tìm kiếm nhị phân:
   • Độ phức tạp thời gian: O(n log n), với n là độ dài của que tính.
   • Độ phức tạp không gian: O(n), với n là độ dài của que tính.
   • Tìm kiếm nhị phân cho phép tìm kiếm giá trị lớn nhất có thể đạt được khi cắt que tính ở mỗi vị trí i trong thời gian O(log n), giúp cải thiện hiệu suất của thuật toán so với phương pháp đệ quy.

Từ đánh giá độ phức tạp của ba thuật toán trên, ta có thể kết luận như sau:

• Nếu độ dài của que tính nhỏ, phương pháp đệ quy có thể được sử dụng để giải quyết bài toán.
• Nếu độ dài của que tính lớn hơn, động programming là phương pháp tối ưu hơn để giải quyết bài toán, vì nó có thể tránh tính toán lại các giá trị đã tính toán trước đó, giúp cải thiện hiệu suất của thuật toán.
• Nếu độ dài của que tính rất lớn, tìm kiếm nhị phân là phương pháp tối ưu nhất để giải quyết bài toán, vì nó cho phép tìm kiếm giá trị lớn nhất có thể đạt được khi cắt que tính ở mỗi vị trí i trong thời gian O(log n), giúp cải thiện hiệu suất của thuật toán so với phương pháp đệ quy và động programming.

Tùy thuộc vào độ lớn của bài toán que tính, chúng ta có thể lựa chọn phương pháp phù hợp để giải quyết vấn đề một cách hiệu quả và tối ưu.