Hiểu bài toán

Bài toán yêu cầu tìm tổng thể tích lớn nhất có thể của các bánh chưng để luộc trong một nồi thể tích V. Đây là bài toán quy hoạch động dạng bài toán cái túi (Knapsack) kinh điển. Với n bánh chưng, mỗi bánh có thể tích v_i, ta cần chọn một tập hợp con các bánh sao cho tổng thể tích không vượt quá V và là lớn nhất.

Các cách tiếp cận

Cách Quy hoạch động (Knapsack)

#include <stdio.h>
#include <string.h>

int main() {
    int n, v;
    scanf("%d %d", &n, &v);

    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // dp[j] = 1 nếu tổng thể tích j có thể đạt được
    // Sử dụng mảng boolean hoặc bitset
    bool dp[v+1];
    memset(dp, false, sizeof(dp));
    dp[0] = true;

    for (int i = 0; i < n; i++) {
        // Duyệt ngược để tránh sử dụng cùng một bánh nhiều lần
        for (int j = v; j >= a[i]; j--) {
            if (dp[j - a[i]]) dp[j] = true;
        }
    }

    int ans = 0;
    // Tìm giá trị j lớn nhất mà dp[j] = true
    for (int i = v; i >= 0; i--) {
        if (dp[i]) { 
            ans = i; 
            break; 
        }
    }

    printf("%d\n", ans);
    return 0;
}

• Time Complexity: O(n * V)
• Space Complexity: O(V)

Sử dụng kỹ thuật quy hoạch động để giải bài toán cái túi 0-1. Mảng dp với dp[j] là giá trị boolean thể hiện liệu có thể đạt được tổng thể tích j hay không. Ban đầu, dp[0] = true (không chọn cái nào). Với mỗi bánh a[i], ta cập nhật mảng dp từ V trở về a[i]. Nếu dp[j - a[i]] đúng thì dp[j] cũng đúng. Sau cùng, ta duyệt từ V giảm dần để tìm giá trị lớn nhất.

Cách Quy hoạch động (Lưu giá trị)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, V;
    cin >> n >> V;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    // dp[i] là tổng thể tích lớn nhất có thể đạt được nhỏ hơn hoặc bằng i
    vector<int> dp(V + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = V; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
        }
    }

    cout << dp[V] << endl;
    return 0;
}

• Time Complexity: O(n * V)
• Space Complexity: O(V)

Đây là biến thể khác của quy hoạch động. dp[j] lưu tổng thể tích lớn nhất có thể đạt được với giới hạn thể tích là j. Công thức cập nhật: dp[j] = max(dp[j], dp[j - v[i]] + v[i]). Ý nghĩa: chọn hoặc không chọn bánh thứ i vào tập hợp có giới hạn thể tích j. Duyệt ngược j để đảm bảo mỗi bánh chỉ được dùng 1 lần.

Cách Brute Force (Quay lui)

#include <stdio.h>

int n, V;
int v[31];
int max_volume = 0;

void Try(int idx, int current_sum) {
    if (current_sum > V) return;
    if (idx == n) {
        if (current_sum > max_volume) max_volume = current_sum;
        return;
    }
    // Thêm bánh thứ idx
    Try(idx + 1, current_sum + v[idx]);
    // Không thêm bánh thứ idx
    Try(idx + 1, current_sum);
}

int main() {
    scanf("%d %d", &n, &V);
    for (int i = 0; i < n; i++) scanf("%d", &v[i]);
    Try(0, 0);
    printf("%d\n", max_volume);
    return 0;
}

• Time Complexity: O(2^n)
• Space Complexity: O(n)

Thử tất cả các khả năng chọn hoặc không chọn từng bánh. Độ phức tạp theo số mũ. Với n=30, số trường hợp là 2^30 ~ 1 tỷ, quá lớn để chạy trong thời gian cho phép. Tuy nhiên, giải pháp này cho thấy cách tiếp cận trực quan nhất và thường được tối ưu hóa (branch and bound) để chạy nhanh hơn trong một số trường hợp đặc biệt hoặc n nhỏ (n<20).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này là bài toán quy hoạch động dạng Knapsack (Balo) kinh điển.
• Với ràng buộc V <= 2000, quy hoạch động O(n*V) là tối ưu và dễ dàng cài đặt.
• Cần duyệt ngược vòng lặp thể tích (từ V về v[i]) để đảm bảo mỗi phần tử chỉ được thêm vào túi một lần duy nhất.

Lỗi thường gặp

• Lỗi duyệt xuôi trong vòng lặp quy hoạch động: Nếu duyệt xuôi, một bánh có thể được chọn nhiều lần (giải bài toán túi đầy vô hạn) thay vì 0-1.
• Quên kiểm tra điều kiện biên khi truy cập mảng (ví dụ: j - v[i] < 0).
• Sử dụng mảng quá nhỏ so với giới hạn V của đề bài.