Bài toán Balo Vô hạn¶

Trong phần này, trước tiên chúng ta sẽ giải quyết một bài toán balo phổ biến khác: balo vô hạn, sau đó khám phá một trường hợp đặc biệt của nó: bài toán đổi tiền xu.

Bài toán Balo Vô hạn¶

Question

Cho \(n\) đồ vật, trong đó trọng lượng của đồ vật thứ \(i\) là \(wgt[i-1]\) và giá trị của nó là \(val[i-1]\), cùng một chiếc balo có sức chứa \(cap\). Mỗi đồ vật có thể được chọn nhiều lần. Hỏi giá trị lớn nhất có thể xếp vào balo trong giới hạn sức chứa là bao nhiêu? Một ví dụ được thể hiện trong hình dưới đây.

Hướng tiếp cận Quy hoạch động¶

Bài toán balo vô hạn rất giống với bài toán balo 0-1, chỉ khác ở chỗ không có giới hạn về số lần một đồ vật có thể được chọn.

Trong bài toán balo 0-1, mỗi loại đồ vật chỉ có duy nhất một cái, vì vậy sau khi bỏ đồ vật \(i\) vào balo, chúng ta chỉ có thể chọn từ \(i-1\) đồ vật đầu tiên.
Trong bài toán balo vô hạn, số lượng của mỗi loại đồ vật là vô hạn, vì vậy sau khi bỏ đồ vật \(i\) vào balo, chúng ta vẫn có thể chọn từ \(i\) đồ vật đầu tiên.

Dưới các quy tắc của bài toán balo vô hạn, các thay đổi của trạng thái \([i, c]\) được chia thành hai trường hợp.

Không bỏ đồ vật \(i\): Tương tự như bài toán balo 0-1, chuyển trạng thái về \([i-1, c]\).
Bỏ đồ vật \(i\): Khác với bài toán balo 0-1, chuyển trạng thái về \([i, c-wgt[i-1]]\).

Do đó, phương trình chuyển trạng thái trở thành:

\[ dp[i, c] = \max(dp[i-1, c], dp[i, c - wgt[i-1]] + val[i-1]) \]

Triển khai mã nguồn¶

So sánh mã nguồn của hai bài toán, có một thay đổi trong quá trình chuyển trạng thái từ \(i-1\) thành \(i\), các phần còn lại hoàn toàn giống nhau:

[file]{unbounded_knapsack}-[class]{}-[func]{unbounded_knapsack_dp}

Tối ưu hóa không gian¶

Vì trạng thái hiện tại được chuyển đổi từ các trạng thái bên trái và phía trên nó, sau khi tối ưu hóa không gian, mỗi dòng trong bảng \(dp\) nên được duyệt theo thứ tự xuôi.

Thứ tự duyệt này hoàn toàn ngược lại so với bài toán balo 0-1. Vui lòng tham khảo hình dưới đây để hiểu sự khác biệt giữa hai phương pháp.

Việc triển khai mã nguồn tương đối đơn giản, chỉ cần xóa chiều thứ nhất của mảng dp:

[file]{unbounded_knapsack}-[class]{}-[func]{unbounded_knapsack_dp_comp}

Bài toán Đổi tiền¶

Bài toán balo đại diện cho một nhóm lớn các bài toán quy hoạch động và có nhiều biến thể, chẳng hạn như bài toán đổi tiền xu.

Question

Cho \(n\) loại tiền xu, trong đó mệnh giá của loại tiền xu thứ \(i\) là \(coins[i - 1]\), và số tiền mục tiêu là \(amt\). Mỗi loại tiền xu có thể được chọn nhiều lần. Hỏi số lượng đồng tiền xu ít nhất cần thiết để tạo thành số tiền mục tiêu là bao nhiêu? Nếu không thể tạo thành số tiền mục tiêu, trả về \(-1\). Một ví dụ được thể hiện trong hình dưới đây.

Hướng tiếp cận Quy hoạch động¶

Bài toán đổi tiền xu có thể được xem như một trường hợp đặc biệt của bài toán balo vô hạn, với những mối liên hệ và điểm khác biệt sau:

Hai bài toán có thể chuyển đổi cho nhau: "đồ vật" tương ứng với "đồng xu", "trọng lượng đồ vật" tương ứng với "mệnh giá đồng xu", và "sức chứa balo" tương ứng với "số tiền mục tiêu".
Các mục tiêu tối ưu hóa là ngược nhau: bài toán balo vô hạn nhằm mục đích tối đa hóa giá trị đồ vật, trong đó bài toán đổi tiền xu nhằm mục đích tối thiểu hóa số lượng đồng tiền xu.
Bài toán balo vô hạn tìm kiếm các giải pháp "không vượt quá" sức chứa balo, trong đó bài toán đổi tiền xu tìm kiếm các giải pháp "chính xác" tạo thành số tiền mục tiêu.

Bước 1: Suy nghĩ về quyết định trong từng vòng, định nghĩa trạng thái, và từ đó có được bảng \(dp\)

Trạng thái \([i, a]\) tương ứng với bài toán con: số lượng đồng tiền xu ít nhất từ \(i\) loại tiền xu đầu tiên để tạo thành số tiền \(a\), được ký hiệu là \(dp[i, a]\).

Bảng \(dp\) hai chiều có kích thước \((n+1) \times (amt+1)\).

Bước 2: Xác định cấu trúc con tối ưu, từ đó rút ra phương trình chuyển trạng thái

Bài toán này khác với bài toán balo vô hạn ở hai khía cạnh sau liên quan đến phương trình chuyển trạng thái:

Bài toán này tìm kiếm giá trị nhỏ nhất, do đó toán tử \(\max()\) cần phải đổi thành \(\min()\).
Mục tiêu tối ưu hóa là số lượng tiền xu thay vì giá trị đồ vật, vì vậy khi một đồng xu được chọn, chúng ta chỉ cần cộng thêm \(1\).

\[ dp[i, a] = \min(dp[i-1, a], dp[i, a - coins[i-1]] + 1) \]

Bước 3: Xác định điều kiện biên và thứ tự chuyển trạng thái

Khi số tiền mục tiêu là \(0\), số lượng tiền xu tối thiểu cần thiết để tạo thành nó là \(0\), do đó tất cả các ô ở cột đầu tiên \(dp[i, 0]\) đều bằng \(0\).

Khi không có tiền xu, không thể tạo thành bất kỳ số tiền nào \(> 0\), đây là một lời giải vô hiệu. Để cho phép hàm \(\min()\) trong phương trình chuyển trạng thái nhận biết và lọc bỏ các lời giải vô hiệu, chúng ta cân nhắc sử dụng \(+ \infty\) để đại diện cho chúng, tức là đặt tất cả các ô ở dòng đầu tiên \(dp[0, a]\) thành \(+ \infty\).

Triển khai mã nguồn¶

Hầu hết các ngôn ngữ lập trình đều không cung cấp biến số \(+ \infty\), và chỉ có thể sử dụng giá trị lớn nhất của kiểu số nguyên int làm giá trị thay thế. Tuy nhiên, điều này có thể dẫn đến tràn số nguyên (integer overflow): phép toán \(+ 1\) trong phương trình chuyển trạng thái có thể gây tràn số.

Vì lý do này, chúng ta sử dụng số \(amt + 1\) để biểu diễn các giải pháp vô hiệu, vì số lượng tiền xu tối đa cần thiết để tạo thành số tiền \(amt\) tối đa là \(amt\) đồng xu. Trước khi trả về kết quả, hãy kiểm tra xem \(dp[n, amt]\) có bằng \(amt + 1\) hay không; nếu có, trả về \(-1\), cho biết số tiền mục tiêu không thể được tạo thành. Mã nguồn như sau:

[file]{coin_change}-[class]{}-[func]{coin_change_dp}

Hình dưới đây cho thấy quy trình quy hoạch động cho bài toán đổi tiền xu, rất giống với bài toán balo vô hạn.

Tối ưu hóa không gian¶

Việc tối ưu hóa không gian cho bài toán đổi tiền xu được xử lý tương tự như bài toán balo vô hạn:

[file]{coin_change}-[class]{}-[func]{coin_change_dp_comp}

Bài toán Đổi tiền II¶

Question

Cho \(n\) loại tiền xu, trong đó mệnh giá của loại tiền xu thứ \(i\) là \(coins[i - 1]\), và số tiền mục tiêu là \(amt\). Mỗi loại tiền xu có thể được chọn nhiều lần. Hỏi có bao nhiêu cách kết hợp (tổ hợp) tiền xu để tạo thành số tiền mục tiêu? Một ví dụ được thể hiện trong hình dưới đây.

Hướng tiếp cận Quy hoạch động¶

So với bài toán trước, mục tiêu của bài toán này là tìm số cách kết hợp tiền xu (tổ hợp), do đó bài toán con trở thành: số cách kết hợp từ \(i\) loại tiền xu đầu tiên để tạo thành số tiền \(a\). Bảng \(dp\) vẫn là một ma trận hai chiều kích thước \((n+1) \times (amt + 1)\).

Số cách kết hợp cho trạng thái hiện tại bằng tổng số cách kết hợp từ việc không chọn đồng tiền hiện tại và việc chọn đồng tiền hiện tại. Phương trình chuyển trạng thái là:

\[ dp[i, a] = dp[i-1, a] + dp[i, a - coins[i-1]] \]

Khi số tiền mục tiêu là \(0\), không cần chọn bất kỳ đồng tiền nào để tạo thành số tiền đó (chỉ có \(1\) cách duy nhất là không chọn đồng nào), vì vậy tất cả các ô ở cột đầu tiên \(dp[i, 0]\) nên được khởi tạo thành \(1\). Khi không có tiền xu, không thể tạo thành bất kỳ số tiền nào \(>0\), vì vậy tất cả các ô ở dòng đầu tiên \(dp[0, a]\) đều bằng \(0\).

Triển khai mã nguồn¶

[file]{coin_change_ii}-[class]{}-[func]{coin_change_ii_dp}

Tối ưu hóa không gian¶

Tối ưu hóa không gian được xử lý theo cách tương tự, chỉ cần xóa đi chiều mệnh giá tiền xu:

[file]{coin_change_ii}-[class]{}-[func]{coin_change_ii_dp_comp}