Bài toán điển hình về thuật toán quy hoạch động

Một ví dụ cụ thể về thuật toán quy hoạch động (Dynamic Programming – DP) là bài toán tìm lợi nhuận tối đa của một chiếc túi với giới hạn trọng lượng và danh sách các món hàng có sẵn.

Ví dụ, giả sử bạn có một chiếc túi với giới hạn trọng lượng là 10 kg và danh sách các món hàng như sau:

Thuật toán quy hoạch động giúp ta tìm ra cách sắp xếp các món hàng trong túi để đạt được lợi nhuận tối đa.

Bước đầu tiên là xác định một bảng DP với chiều dài bằng giới hạn trọng lượng của chiếc túi và chiều rộng bằng số lượng các món hàng. Giá trị của mỗi ô trong bảng DP là giá trị lớn nhất có thể đạt được khi chọn một số lượng các món hàng từ 1 đến i, và giới hạn trọng lượng là j.

Ví dụ, ô DP[3][6] sẽ có giá trị là lợi nhuận tối đa có thể đạt được khi chọn từ các món hàng A, B và C, với giới hạn trọng lượng của túi là 6 kg.

Sau khi xác định được bảng DP, ta sử dụng công thức truy hồi để tính toán giá trị của mỗi ô. Công thức này sẽ lấy giá trị của ô trước đó trong cùng hàng (tức là khi chưa chọn món hàng i), và so sánh với giá trị của ô khi đã chọn món hàng i (tức là khi đã sử dụng trọng lượng của món hàng i và tính toán lợi nhuận từ các món hàng còn lại).

Sau khi tính toán giá trị của tất cả các ô trong bảng DP, giá trị của ô cuối cùng DP[10][5] sẽ cho biết lợi nhuận tối đa có thể đạt được khi sử dụng toàn bộ giới hạn trọng lượng của túi và các món hàng có sẵn.

Dưới đây là code C++ cho bài toán tìm lợi nhuận tối đa của một chiếc túi với giới hạn trọng lượng và danh sách các món hàng có sẵn, sử dụng thuật toán quy hoạch động:

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

const int MAX_N = 100; // số lượng món hàng tối đa
const int MAX_W = 100; // trọng lượng tối đa của túi
int N, W; // N là số lượng món hàng, W là trọng lượng tối đa của túi
int w[MAX_N], v[MAX_N]; // w là danh sách trọng lượng các món hàng, v là danh sách giá trị các món hàng
int dp[MAX_N+1][MAX_W+1]; // bảng DP

int main() {
    // Nhập dữ liệu
    cin >> N >> W;
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }

    // Khởi tạo bảng DP
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (j >= w[i-1]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // In ra kết quả
    cout << dp[N][W] << endl;
    return 0;
}