Bí kíp giải bài toán xếp ba lô (bài toán cái túi) với C++

Bài toán xếp ba lô (hay còn gọi là bài toán cái túi) là một bài toán tối ưu hóa tổ hợp. Nó xuất phát từ việc chọn những vật phẩm quan trọng nhất để đặt vào một cái túi có giới hạn trọng lượng, nhằm mang theo trong một chuyến đi. Đây là một bài toán phổ biến trong kinh doanh.

Vấn đề:
Một tên trộm xâm nhập vào một cửa hàng và phát hiện có n mặt hàng có trọng lượng và giá trị khác nhau. Tuy nhiên, hắn chỉ mang theo một cái túi có khối lượng tối đa là m. Vậy tên trộm cần lựa chọn những vật phẩm nào và số lượng bao nhiêu để đạt được giá trị cao nhất có thể mà hắn có thể mang đi?

Yêu cầu: Tìm tổng giá trị đồ vật lớn nhất mà tên trộm có thể mang đi.

Bạn đang xem: Bí kíp giải bài toán xếp ba lô (bài toán cái túi) với C++

Giải pháp:

• Đầu vào: Số nguyên dương n và m (n ≤ 20, m ≤ 10^9).
• Trong n dòng tiếp theo, dòng thứ i ghi số nguyên dương ai và bi (ai, bi ≤ 10^9).
• Kết quả: Ghi ra một dòng duy nhất ghi tổng giá trị đồ vật lớn nhất mà tên trộm có thể mang đi được.

Code tham khảo:

#include 
#include 
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector weights(n);
    vector values(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i] >> values[i];
    }

    vector> dp(n + 1, vector(m + 1, 0));

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (weights[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

Với ví dụ trên, chương trình sẽ đọc dữ liệu từ tệp DRSEM.INP và ghi kết quả vào tệp DRSEM.OUT. Đầu vào bao gồm số lượng đồ vật n, khối lượng tối đa m, và danh sách n đồ vật với trọng lượng và giá trị tương ứng. Chương trình sử dụng một bảng hai chiều dp để lưu trữ giá trị tối ưu cho mỗi trường hợp con của bài toán.

Kết quả là tổng giá trị lớn nhất mà tên trộm có thể mang đi được, được ghi vào tệp DRSEM.OUT.

Vui lòng tạo tệp DRSEM.INP và nhập dữ liệu đầu vào theo đúng định dạng để chạy chương trình. Sau khi chạy, bạn sẽ có kết quả trong tệp DRSEM.OUT.

Cách giải khác:
Một cách khác để giải bài toán xếp ba lô là sử dụng thuật toán quay lui. Bằng cách này, chúng ta có thể áp dụng một hàm đệ quy để thử tất cả các khả năng chọn hoặc không chọn từng vật phẩm. Dưới đây là một ví dụ về cách giải quyết bài toán này bằng thuật toán quay lui:

#include 
#include 
using namespace std;

int maxTotalValue = 0;

void backtrack(vector& selectedItems, vector& weights, vector& values, int remainingWeight, int totalValue, int currentItem) {
    if (currentItem >= weights.size() || remainingWeight == 0) {
        if (totalValue > maxTotalValue) {
            maxTotalValue = totalValue;
        }
        return;
    }

    if (weights[currentItem] <= remainingWeight) {
        selectedItems[currentItem] = 1;
        backtrack(selectedItems, weights, values, remainingWeight - weights[currentItem], totalValue + values[currentItem], currentItem + 1);
        selectedItems[currentItem] = 0;
    }

    backtrack(selectedItems, weights, values, remainingWeight, totalValue, currentItem + 1);
}

int main() {
    int n, m;
    cin >> n >> m;

    vector weights(n);
    vector values(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i] >> values[i];
    }

    vector selectedItems(n, 0);

    backtrack(selectedItems, weights, values, m, 0, 0);

    cout << maxTotalValue << endl;

    return 0;
}

Với ví dụ trên, chương trình sẽ đọc dữ liệu từ tệp DRSEM.INP và ghi kết quả vào tệp DRSEM.OUT. Đầu vào bao gồm số lượng đồ vật n, khối lượng tối đa m, và danh sách n đồ vật với trọng lượng và giá trị tương ứng. Chương trình sử dụng một mảng selectedItems để lưu trữ các vật phẩm được chọn và một biến maxTotalValue để lưu trữ giá trị tối đa.

Kết quả là tổng giá trị lớn nhất mà tên trộm có thể mang đi được, được ghi vào tệp DRSEM.OUT.

Nguồn: https://izumi.edu.vn/
Danh mục: Tài liệu toán