Bài 26.5. Bài tập tổng hợp về quy hoạch động cơ bản

Chào mừng các bạn quay trở lại với series về Cấu trúc dữ liệu và Giải thuật! Chúng ta đã cùng nhau tìm hiểu về Quy hoạch động (Dynamic Programming - DP) - một kỹ thuật cực kỳ mạnh mẽ để giải quyết các bài toán tối ưu và đếm phức tạp bằng cách chia nhỏ chúng thành các bài toán con.

Lý thuyết chỉ là bước đầu. Để thực sự nắm vững DP, chúng ta cần phải luyện tập thật nhiều! Bài viết hôm nay sẽ tổng hợp một số bài tập cơ bản nhưng kinh điển về Quy hoạch động, giúp bạn củng cố lại kiến thức và làm quen với cách nhận diện, định nghĩa trạng thái và xây dựng công thức truy hồi cho các bài toán DP.

Chúng ta sẽ đi qua từng bài toán, phân tích cách áp dụng DP, và xem xét cài đặt bằng C++.

1. Bài toán Fibonacci

Đây là bài toán kinh điển để giới thiệu về DP vì nó minh họa rất rõ khái niệm bài toán con gối nhau (overlapping subproblems).

Đề bài: Tính số Fibonacci thứ n, ký hiệu là F(n). Dãy Fibonacci được định nghĩa như sau: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) với n > 1.

Phân tích DP:

Bài toán con: Để tính F(n), ta cần tính F(n-1) và F(n-2). Để tính F(n-1), ta cần F(n-2) và F(n-3), v.v. Rõ ràng có rất nhiều bài toán con như F(n-2), F(n-3),... được tính lặp đi lặp lại. Đây chính là đặc điểm bài toán con gối nhau.
Tối ưu/Đếm: Bài này là bài toán đếm/tính giá trị.
Công thức truy hồi: Đề bài đã cho sẵn: F(n) = F(n-1) + F(n-2).
Trạng thái: Trạng thái đơn giản chính là số thứ tự i trong dãy Fibonacci. Ta cần lưu trữ giá trị F(i) cho mỗi i.

Cài đặt bằng C++ (Bottom-Up Tabulation): Chúng ta sẽ xây dựng một mảng dp mà dp[i] lưu giá trị F(i). Ta tính từ các giá trị gốc (F(0), F(1)) và đi dần lên đến F(n).

#include <iostream>
#include <vector>

// Sử dụng phương pháp Bottom-Up (Tabulation)
int fibonacci_dp(int n) {
    if (n <= 1) {
        return n;
    }

    // Khởi tạo mảng DP. dp[i] sẽ lưu giá trị F(i)
    std::vector<int> dp(n + 1);

    // Thiết lập các giá trị cơ sở
    dp[0] = 0;
    dp[1] = 1;

    // Lấp đầy mảng DP sử dụng công thức truy hồi
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // Kết quả cuối cùng là dp[n]
    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "So Fibonacci thu " << n << " la: " << fibonacci_dp(n) << std::endl; // Output: 55
    return 0;
}

Giải thích code:

Ta kiểm tra trường hợp cơ bản n <= 1 trả về n ngay lập tức.
Tạo một vector dp có kích thước n + 1. dp[i] sẽ lưu trữ giá trị Fibonacci thứ i.
Thiết lập hai giá trị cơ sở đã biết: dp[0] = 0 và dp[1] = 1.
Sử dụng vòng lặp for từ i = 2 đến n. Tại mỗi bước, ta tính dp[i] dựa vào hai giá trị trước đó trong mảng theo công thức dp[i] = dp[i - 1] + dp[i - 2].
Sau khi vòng lặp kết thúc, dp[n] chính là giá trị Fibonacci thứ n.

Cách này tránh được việc tính toán đi tính toán lại các giá trị Fibonacci con, hiệu quả hơn rất nhiều so với đệ quy thuần túy khi n lớn. Độ phức tạp thời gian là O(n) và độ phức tạp không gian là O(n). Ta còn có thể tối ưu không gian xuống O(1) bằng cách chỉ lưu hai giá trị trước đó.

2. Bài toán Leo cầu thang (Climbing Stairs)

Một bài toán khác cũng có cấu trúc tương tự Fibonacci.

Đề bài: Bạn đang leo lên một cầu thang có n bậc. Mỗi lần, bạn có thể bước 1 hoặc 2 bậc. Hỏi có bao nhiêu cách khác nhau để leo đến đỉnh cầu thang?

Phân tích DP:

Bài toán con: Để leo đến bậc n, bước cuối cùng của bạn có thể là:
- Bước 1 bậc từ bậc n-1. Số cách để đến bậc n trong trường hợp này bằng số cách để đến bậc n-1.
- Bước 2 bậc từ bậc n-2. Số cách để đến bậc n trong trường hợp này bằng số cách để đến bậc n-2. Tổng số cách để đến bậc n là tổng số cách của hai trường hợp trên.
Tối ưu/Đếm: Đây là bài toán đếm số cách.
Công thức truy hồi: Gọi dp[i] là số cách để leo đến bậc i. Dựa vào phân tích trên, ta có dp[i] = dp[i-1] + dp[i-2] cho i > 2.
Trạng thái: Trạng thái là số bậc thang i. dp[i] lưu số cách để đến bậc i.
Trường hợp cơ sở:
- dp[0] = 1 (Có 1 cách để ở lại bậc 0 - không làm gì cả, hoặc coi là điểm bắt đầu).
- dp[1] = 1 (Có 1 cách để đến bậc 1: bước 1 bậc từ bậc 0).
- dp[2] = 2 (Có 2 cách để đến bậc 2: 1+1 hoặc 2). Lưu ý công thức dp[i] = dp[i-1] + dp[i-2] cũng đúng với i=2: dp[2] = dp[1] + dp[0] = 1 + 1 = 2.

Cài đặt bằng C++ (Bottom-Up Tabulation):

#include <iostream>
#include <vector>

int climbStairs(int n) {
    if (n <= 1) {
        return 1; // 1 cách để đến bậc 0 (ở yên) hoặc 1 cách để đến bậc 1 (bước 1)
    }

    // dp[i] sẽ lưu số cách để đến bậc i
    std::vector<int> dp(n + 1);

    // Thiết lập các trường hợp cơ sở
    dp[0] = 1; // Có 1 cách để ở bậc 0
    dp[1] = 1; // Có 1 cách để đến bậc 1

    // Lấp đầy mảng DP
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // Kết quả là số cách để đến bậc n
    return dp[n];
}

int main() {
    int n = 5;
    std::cout << "So cach de leo len " << n << " bac thang la: " << climbStairs(n) << std::endl; // Output: 8
    // F(0)=1, F(1)=1, F(2)=2, F(3)=3, F(4)=5, F(5)=8
    return 0;
}

Giải thích code:

Xử lý các trường hợp cơ bản n <= 1.
Tạo mảng dp kích thước n + 1.
Thiết lập dp[0] = 1 và dp[1] = 1 (số cách đến bậc 0 và 1).
Vòng lặp từ i = 2 đến n để tính số cách đến các bậc tiếp theo. dp[i] được tính bằng tổng số cách đến bậc i-1 và i-2.
Trả về dp[n].

Bài toán này về bản chất giống hệt Fibonacci, chỉ khác ở định nghĩa trường hợp cơ sở F(0). Độ phức tạp tương tự Fibonacci: O(n) thời gian và O(n) không gian (có thể tối ưu xuống O(1) không gian).

3. Bài toán Đổi tiền xu (Coin Change - Minimum Coins)

Bài toán này minh họa cách DP có thể được sử dụng để tìm giá trị tối thiểu.

Đề bài: Cho một tập hợp các mệnh giá tiền xu coins và một tổng số tiền amount. Tìm số lượng tiền xu ít nhất cần thiết để đổi được tổng số tiền amount. Nếu không thể đổi được, trả về -1.

Phân tích DP:

Bài toán con: Để đổi được số tiền i, ta có thể dùng một đồng xu có mệnh giá c nào đó (từ tập coins). Nếu ta dùng đồng xu c, thì bài toán còn lại là đổi số tiền i - c. Số xu cần thiết trong trường hợp này sẽ là 1 (cho đồng xu c) cộng với số xu tối thiểu để đổi i - c. Ta muốn tìm minimum số xu, nên ta sẽ thử tất cả các loại đồng xu c và lấy kết quả nhỏ nhất.
Tối ưu/Đếm: Đây là bài toán tối ưu (tìm số lượng xu ít nhất).
Công thức truy hồi: Gọi dp[i] là số lượng tiền xu tối thiểu để đổi được số tiền i. dp[i] = min(dp[i], dp[i - coin] + 1) cho mỗi coin trong tập coins sao cho i >= coin.
Trạng thái: Trạng thái là tổng số tiền i cần đổi. dp[i] lưu số xu tối thiểu cho số tiền i.
Trường hợp cơ sở: dp[0] = 0 (cần 0 xu để đổi 0 đồng). Đối với các số tiền i > 0 ban đầu, ta sẽ gán giá trị "vô cùng" (hoặc một giá trị rất lớn) để biểu thị rằng chưa biết cách đổi hoặc không thể đổi được.

Cài đặt bằng C++ (Bottom-Up Tabulation):

#include <iostream>
#include <vector>
#include <algorithm> // For std::min
#include <limits>    // For std::numeric_limits

int coinChange(std::vector<int>& coins, int amount) {
    // dp[i] sẽ lưu số lượng xu tối thiểu để đổi được số tiền i
    // Khởi tạo với một giá trị lớn (vô cùng) để biểu thị không thể đổi
    // dp size = amount + 1 để chứa các giá trị từ 0 đến amount
    std::vector<int> dp(amount + 1, std::numeric_limits<int>::max());

    // Trường hợp cơ sở: cần 0 xu để đổi 0 đồng
    dp[0] = 0;

    // Lấp đầy mảng DP từ 1 đến amount
    for (int i = 1; i <= amount; ++i) {
        // Thử từng loại đồng xu
        for (int coin : coins) {
            // Nếu số tiền i đủ lớn để dùng đồng xu này
            // và đã có cách đổi cho số tiền (i - coin) (tức dp[i - coin] không phải là vô cùng)
            if (i >= coin && dp[i - coin] != std::numeric_limits<int>::max()) {
                // Cập nhật dp[i] bằng cách lấy min(số xu hiện tại, số xu để đổi i-coin + 1)
                dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // Nếu dp[amount] vẫn là giá trị lớn ban đầu, nghĩa là không thể đổi được
    return dp[amount] == std::numeric_limits<int>::max() ? -1 : dp[amount];
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    int min_coins = coinChange(coins, amount);

    if (min_coins != -1) {
        std::cout << "So xu toi thieu de doi " << amount << " la: " << min_coins << std::endl; // Output: 3 (11 = 5 + 5 + 1)
    } else {
        std::cout << "Khong the doi " << amount << std::endl;
    }

    std::vector<int> coins2 = {2};
    int amount2 = 3;
    int min_coins2 = coinChange(coins2, amount2);
     if (min_coins2 != -1) {
        std::cout << "So xu toi thieu de doi " << amount2 << " la: " << min_coins2 << std::endl;
    } else {
        std::cout << "Khong the doi " << amount2 << std::endl; // Output: Khong the doi 3
    }

    return 0;
}

Giải thích code:

Tạo vector dp kích thước amount + 1 và khởi tạo tất cả các phần tử với một giá trị rất lớn (std::numeric_limits<int>::max()) để biểu thị rằng chưa có cách đổi.
Thiết lập dp[0] = 0 vì cần 0 xu để đổi 0 đồng.
Vòng lặp ngoài chạy từ i = 1 đến amount. i đại diện cho số tiền hiện tại ta đang cố gắng đổi.
Vòng lặp trong duyệt qua từng loại đồng xu trong tập coins.
Bên trong vòng lặp trong, ta kiểm tra xem nếu dùng đồng xu coin này cho số tiền i, thì phần còn lại là i - coin. Điều kiện i >= coin đảm bảo i - coin không âm. Điều kiện dp[i - coin] != std::numeric_limits<int>::max() đảm bảo rằng có cách để đổi được số tiền i - coin (nếu không, việc cộng thêm 1 xu coin này cũng không giúp đổi được i).
Nếu cả hai điều kiện đều đúng, ta cập nhật dp[i] bằng cách so sánh giá trị hiện tại của dp[i] với số xu cần thiết nếu dùng đồng xu coin (dp[i - coin] + 1). Ta lấy giá trị nhỏ hơn.
Sau khi duyệt qua tất cả các đồng xu cho số tiền i, dp[i] sẽ chứa số xu tối thiểu để đổi i (hoặc vẫn là giá trị lớn ban đầu nếu không thể đổi).
Cuối cùng, kiểm tra dp[amount]. Nếu nó vẫn là giá trị lớn, trả về -1; ngược lại, trả về dp[amount].

Độ phức tạp thời gian là O(amount \ |coins|). Độ phức tạp không gian là O(amount)*.

4. Bài toán Dãy con tăng dài nhất (Longest Increasing Subsequence - LIS)

Bài toán này chuyển sang tìm một dãy con có tính chất nhất định và tối ưu hóa độ dài.

Đề bài: Cho một mảng các số nguyên nums. Tìm độ dài của dãy con tăng dài nhất (LIS). Một dãy con là một dãy mới được tạo ra từ mảng gốc bằng cách xóa đi (hoặc không xóa) bất kỳ phần tử nào mà không làm thay đổi thứ tự của các phần tử còn lại.

Phân tích DP (O(n^2)):

Bài toán con: Để tìm LIS kết thúc tại phần tử nums[i], ta cần xem xét tất cả các phần tử nums[j] đứng trước nó (j < i). Nếu nums[j] < nums[i], thì nums[i] có thể nối tiếp một LIS kết thúc tại nums[j]. Độ dài của LIS kết thúc tại nums[i] khi nối từ nums[j] sẽ là độ dài của LIS kết thúc tại nums[j] cộng thêm 1. Ta muốn tìm LIS dài nhất kết thúc tại nums[i], nên ta sẽ lấy giá trị lớn nhất trong số các khả năng nối tiếp từ các nums[j] hợp lệ.
Tối ưu/Đếm: Đây là bài toán tối ưu (tìm độ dài lớn nhất).
Công thức truy hồi: Gọi dp[i] là độ dài của dãy con tăng dài nhất kết thúc tại chỉ số i. dp[i] = 1 + max(dp[j]) cho tất cả j < i sao cho nums[j] < nums[i]. Nếu không có j < i nào thỏa mãn nums[j] < nums[i], thì LIS kết thúc tại nums[i] chỉ có mỗi nums[i], nên dp[i] = 1.
Trạng thái: Trạng thái là chỉ số i của phần tử trong mảng gốc. dp[i] lưu độ dài LIS kết thúc tại nums[i].
Trường hợp cơ sở: Mọi phần tử đều có thể tạo thành một LIS có độ dài ít nhất là 1 (chính nó). Do đó, ta khởi tạo tất cả dp[i] = 1.
Kết quả cuối cùng: Độ dài LIS của toàn bộ mảng là giá trị lớn nhất trong mảng dp.

Cài đặt bằng C++ (O(n^2) Bottom-Up):

#include <iostream>
#include <vector>
#include <algorithm> // For std::max_element

int lengthOfLIS(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }

    // dp[i] sẽ lưu độ dài của LIS kết thúc tại chỉ số i
    std::vector<int> dp(n, 1); // Khởi tạo mỗi dp[i] = 1 (phần tử tại i tự nó là LIS độ dài 1)

    // Lấp đầy mảng DP
    // Vòng lặp ngoài: Xét từng phần tử nums[i] từ trái sang phải
    for (int i = 1; i < n; ++i) {
        // Vòng lặp trong: Xét tất cả các phần tử nums[j] đứng trước nums[i]
        for (int j = 0; j < i; ++j) {
            // Nếu nums[i] lớn hơn nums[j], nghĩa là nums[i] có thể nối tiếp LIS kết thúc tại nums[j]
            if (nums[i] > nums[j]) {
                // Cập nhật dp[i]: Lấy giá trị lớn nhất giữa dp[i] hiện tại
                // và (độ dài LIS kết thúc tại j + 1)
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    // Độ dài LIS toàn cục là giá trị lớn nhất trong mảng dp
    // std::max_element trả về iterator, ta cần dereference (*) để lấy giá trị
    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    std::cout << "Do dai LIS la: " << lengthOfLIS(nums) << std::endl; // Output: 4 (vi du: 2, 3, 7, 18 hoac 2, 5, 7, 101)

    std::vector<int> nums2 = {0, 1, 0, 3, 2, 3};
    std::cout << "Do dai LIS la: " << lengthOfLIS(nums2) << std::endl; // Output: 4 (vi du: 0, 1, 2, 3)

    std::vector<int> nums3 = {7, 7, 7, 7, 7, 7, 7};
    std::cout << "Do dai LIS la: " << lengthOfLIS(nums3) << std::endl; // Output: 1

    return 0;
}

Giải thích code:

Xử lý trường hợp mảng rỗng.
Tạo vector dp có kích thước n (kích thước của nums) và khởi tạo tất cả phần tử bằng 1.
Vòng lặp ngoài duyệt qua mảng nums từ chỉ số 1 đến n-1. Với mỗi phần tử nums[i], ta cố gắng tính dp[i].
Vòng lặp trong duyệt qua tất cả các chỉ số j từ 0 đến i-1.
Nếu nums[i] > nums[j], nghĩa là nums[i] có thể đứng sau nums[j] trong một dãy con tăng.
Ta cập nhật dp[i] bằng max(dp[i], dp[j] + 1). dp[i] ban đầu là 1 (LIS chỉ có nums[i]). dp[j] + 1 là độ dài LIS kết thúc tại nums[i] nếu nó nối tiếp LIS kết thúc tại nums[j]. Ta lấy giá trị lớn nhất vì muốn tìm LIS dài nhất kết thúc tại nums[i].
Sau khi hai vòng lặp kết thúc, mảng dp chứa độ dài LIS kết thúc tại mỗi vị trí. Độ dài LIS của cả mảng chính là giá trị lớn nhất trong dp.
Sử dụng *std::max_element(dp.begin(), dp.end()) để tìm và trả về giá trị lớn nhất trong dp.

Độ phức tạp thời gian của cách làm này là O(n^2) do có hai vòng lặp lồng nhau. Độ phức tạp không gian là O(n). Tồn tại thuật toán DP + Binary Search có độ phức tạp O(n log n) nhưng nó phức tạp hơn và thường được xem là biến thể nâng cao hơn một chút của bài LIS.

5. Bài toán Cái túi 0/1 (0/1 Knapsack)

Đây là một bài toán tối ưu kinh điển, thường được giải bằng DP.

Đề bài: Cho n món đồ, mỗi món có một trọng lượng w_i và giá trị v_i. Bạn có một cái túi có sức chứa tối đa W. Hãy chọn một tập hợp các món đồ để đưa vào túi sao cho tổng giá trị của các món đồ là lớn nhất, với điều kiện tổng trọng lượng của chúng không vượt quá sức chứa W. Mỗi món đồ chỉ có thể chọn một lần hoặc không chọn (đây là lý do gọi là 0/1 Knapsack).

Phân tích DP:

Bài toán con: Để giải bài toán cho i món đồ và sức chứa j, ta có hai lựa chọn đối với món đồ thứ i:
1. Không chọn món đồ thứ i: Tổng giá trị sẽ bằng tổng giá trị tối đa khi giải bài toán với i-1 món đồ và sức chứa j.
2. Chọn món đồ thứ i (nếu trọng lượng của nó w_i không vượt quá j): Tổng giá trị sẽ bằng giá trị của món đồ thứ i (v_i) cộng với tổng giá trị tối đa khi giải bài toán với i-1 món đồ và sức chứa còn lại là j - w_i.
Tối ưu/Đếm: Bài toán tối ưu (tìm tổng giá trị lớn nhất).
Công thức truy hồi: Gọi dp[i][j] là tổng giá trị lớn nhất có thể đạt được khi chỉ sử dụng i món đồ đầu tiên và túi có sức chứa j.
- Nếu weights[i-1] > j (món đồ thứ i quá nặng so với sức chứa j), ta không thể chọn nó: dp[i][j] = dp[i-1][j].
- Nếu weights[i-1] <= j (món đồ thứ i có thể chọn hoặc không chọn): dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j - weights[i-1]]). Lấy giá trị lớn nhất giữa việc không chọn và có chọn món đồ thứ i. (Lưu ý: dùng i-1 cho mảng weights và values nếu chúng là 0-indexed).
Trạng thái: Trạng thái cần hai thông tin: số lượng món đồ đã xét (i) và sức chứa hiện tại của túi (j). dp[i][j] lưu giá trị tối đa.
Trường hợp cơ sở:
- dp[0][j] = 0 cho mọi j (nếu không có món đồ nào, giá trị luôn là 0).
- dp[i][0] = 0 cho mọi i (nếu sức chứa túi là 0, giá trị luôn là 0).

Cài đặt bằng C++ (Bottom-Up Tabulation):

#include <iostream>
#include <vector>
#include <algorithm> // For std::max

int knapSack(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size(); // Số lượng món đồ

    // Tạo bảng DP 2D: dp[i][j] = giá trị lớn nhất khi xét i món đồ đầu tiên với sức chứa j
    // Kích thước (n+1) x (W+1)
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    // Xây dựng bảng dp
    // Vòng lặp ngoài: xét từng món đồ từ 1 đến n
    for (int i = 1; i <= n; ++i) {
        // Vòng lặp trong: xét từng mức sức chứa từ 0 đến W
        for (int j = 0; j <= W; ++j) {
            // Trọng lượng của món đồ thứ i (sử dụng index i-1 cho vector 0-indexed)
            int current_weight = weights[i - 1];
            // Giá trị của món đồ thứ i
            int current_value = values[i - 1];

            // Trường hợp 1: Không chọn món đồ thứ i
            // Giá trị bằng với giá trị khi chỉ xét i-1 món đồ với cùng sức chứa j
            dp[i][j] = dp[i - 1][j];

            // Trường hợp 2: Có thể chọn món đồ thứ i (nếu sức chứa j đủ lớn)
            if (current_weight <= j) {
                // Giá trị nếu chọn món đồ thứ i = giá trị của món đó + giá trị tối đa khi xét i-1 món đồ với sức chứa còn lại (j - current_weight)
                int value_if_included = current_value + dp[i - 1][j - current_weight];

                // Cập nhật dp[i][j] bằng giá trị lớn nhất giữa không chọn và có chọn
                dp[i][j] = std::max(dp[i][j], value_if_included);
            }
        }
    }

    // Kết quả cuối cùng là giá trị tại dp[n][W]
    return dp[n][W];
}

int main() {
    std::vector<int> values = {60, 100, 120};
    std::vector<int> weights = {10, 20, 30};
    int W = 50; // Sức chứa của túi
    int max_value = knapSack(W, weights, values);
    std::cout << "Tong gia tri lon nhat co the mang theo la: " << max_value << std::endl; // Output: 220 (chon item 2 (100) va item 3 (120), tong KL 50)

    return 0;
}

Giải thích code:

Lấy số lượng món đồ n.
Tạo một bảng DP 2D dp có kích thước (n + 1) x (W + 1). dp[i][j] sẽ lưu giá trị tối đa khi xét i món đồ đầu tiên với sức chứa j. Khởi tạo tất cả các giá trị bằng 0 (trường hợp cơ sở khi không có đồ hoặc túi rỗng).
Vòng lặp ngoài duyệt qua số lượng món đồ từ 1 đến n (biến i). Món đồ thứ i tương ứng với index i-1 trong vector weights và values.
Vòng lặp trong duyệt qua sức chứa của túi từ 0 đến W (biến j).
Trong mỗi ô dp[i][j], ta xét món đồ thứ i (với trọng lượng weights[i-1] và giá trị values[i-1]).
Ban đầu, gán dp[i][j] = dp[i-1][j]. Điều này tương ứng với việc không chọn món đồ thứ i. Giá trị tối đa sẽ giống như khi ta chỉ xét i-1 món đồ với cùng sức chứa j.
Kiểm tra xem có thể chọn món đồ thứ i hay không: if (weights[i-1] <= j).
Nếu có thể, tính giá trị nếu chọn món đồ thứ i: values[i-1] + dp[i-1][j - weights[i-1]]. Đây là giá trị của món đồ hiện tại cộng với giá trị tối đa từ i-1 món đồ với sức chứa còn lại sau khi đã cho món đồ thứ i vào túi.
So sánh giá trị khi không chọn (dp[i-1][j]) và giá trị khi có chọn (nếu có thể), và lấy giá trị lớn nhất để cập nhật dp[i][j].
Sau khi hoàn thành cả hai vòng lặp, dp[n][W] sẽ chứa tổng giá trị lớn nhất có thể đạt được khi xét tất cả n món đồ với sức chứa W.

Độ phức tạp thời gian của thuật toán này là O(n \ W). Độ phức tạp không gian là O(n * W). Lưu ý rằng W* là giá trị sức chứa, không phải số lượng bit của nó, nên nếu W rất lớn, thuật toán này có thể chậm. Đây là đặc điểm của bài toán Knapsack 0/1 khi giải bằng DP cổ điển.

Bài tập ví dụ:

Tổng không liền kề.

Cho mảng A[] gồm N phần tử, nhiệm vụ của bạn là tính tổng lớn nhất của dãy con trong mảng với một điều kiện đó là trong dãy con này không được có 2 phần tử nằm liền kề nhau.

Input Format

Dòng đầu tiên là N : số lượng phần tử trong mảng; Dòng thứ 2 là A[i].(1<=N<=10^6; 1<=A[i]<=1000)

Constraints

Output Format

In ra kết quả của bài toán.

Ví dụ:

Dữ liệu vào

5
123 341 100 345 865

Dữ liệu ra

Baik, ini panduan singkat untuk menyelesaikan soal "Total Tidak Bersebelahan" menggunakan C++:

Identifikasi Masalah: Ini adalah masalah optimasi pada urutan, yang seringkali dapat diselesaikan dengan Pemrograman Dinamis (Dynamic Programming - DP). Kita perlu membuat pilihan di setiap elemen (A[i]) - apakah akan memasukkannya ke dalam jumlah atau tidak - dengan mempertimbangkan batasan (tidak boleh dua elemen bersebelahan).
Definisikan Status DP: Untuk elemen ke-i (misal A[i]), kita perlu tahu dua hal:
- Jumlah maksimum yang berakhir di A[i] dengan memasukkan A[i].
- Jumlah maksimum yang berakhir di A[i] tanpa memasukkan A[i].
Buat Relasi Rekurensi:
- Jika kita memasukkan A[i], maka kita tidak boleh memasukkan A[i-1]. Jadi, jumlah maksimum saat ini (dengan memasukkan A[i]) adalah jumlah maksimum sebelumnya tanpa memasukkan A[i-1], ditambah A[i] itu sendiri.
- Jika kita tidak memasukkan A[i], maka jumlah maksimum saat ini (tanpa memasukkan A[i]) adalah jumlah maksimum sebelumnya (sampai A[i-1]), baik A[i-1] dimasukkan atau tidak. Kita ambil yang terbesar dari keduanya.
Basis (Base Case): Mulai dari elemen pertama (A[0]).
- Jumlah maksimum dengan memasukkan A[0] adalah A[0].
- Jumlah maksimum tanpa memasukkan A[0] adalah 0.
Iterasi: Lakukan perhitungan dari elemen kedua (A[1]) hingga terakhir (A[N-1]) menggunakan relasi rekurensi. Simpan dua nilai status DP (termasuk A[i] dan tidak termasuk A[i]) saat Anda bergerak maju.
Optimasi Ruang: Perhatikan bahwa status untuk A[i] hanya bergantung pada status untuk A[i-1]. Ini berarti Anda tidak perlu menyimpan seluruh larik DP. Cukup simpan nilai status untuk posisi sebelumnya. Anda hanya butuh dua variabel untuk melacak status "termasuk sebelumnya" dan "tidak termasuk sebelumnya".
Hasil Akhir: Setelah memproses semua elemen, jawaban akhirnya adalah nilai maksimum antara jumlah maksimum yang berakhir dengan memasukkan elemen terakhir dan jumlah maksimum yang tidak memasukkan elemen terakhir.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.