Bài toán đổi tiền xu

Người thu ngân khi trả tiền thừa sẽ lấy đồng xu lớn nhất còn vừa, rồi đến đồng tiếp theo, và với euro hay đô la cách này luôn cho số đồng xu ít nhất. Nhưng nếu đổi các đồng xu thành 1, 3 và 4, cùng thói quen ấy sẽ trả 6 bằng ba đồng trong khi hai đồng là đủ. Quy hoạch động tìm ra giá trị nhỏ nhất thực sự với bất kỳ bộ xu nào.

Một hàng các số tiền, mỗi số kèm số đồng xu ít nhất tạo nên nó, phía trên những đồng xu có ba kích cỡ khác nhau
Một hàng các số tiền, mỗi số kèm số đồng xu ít nhất tạo nên nó, phía trên những đồng xu có ba kích cỡ khác nhau

Hai câu hỏi

Bài toán đổi tiền xu có hai dạng. Dạng thứ nhất hỏi số đồng xu ít nhất tạo nên đúng một số tiền; dạng này còn gọi là bài toán trả tiền thừa. Dạng thứ hai hỏi có bao nhiêu tổ hợp đồng xu khác nhau tạo nên số tiền đó. Ở cả hai dạng, mỗi loại đồng xu được dùng bao nhiêu lần tùy ý, và cả hai đều được giải bằng cách xây dựng đáp án cho mỗi số tiền từ đáp án của các số tiền nhỏ hơn.

Ít xu nhất, từng bước một

Tạo một hàng ô cho các số tiền từ 0 đến số tiền đích. Số tiền 0 cần 0 đồng xu; mọi số tiền khác bắt đầu từ vô cùng. Đi qua các số tiền theo thứ tự, và với mỗi số tiền, thử mọi đồng xu c còn vừa: ô của số tiền trừ c, cộng thêm một đồng xu, là một ứng viên. Giữ lại giá trị nhỏ nhất. Mỗi ô chỉ phụ thuộc vào các ô bên trái nó, vốn đã cố định, nên chỉ một lượt là điền đầy hàng.

Một ví dụ

Với các đồng xu 1, 3 và 4: số tiền 1 cần 1 đồng xu, 2 cần 2, 3 cần 1 (một đồng 3) và 4 cần 1. Với 5, thử 1 (4 cần 1, vậy 2 đồng xu), 3 (2 cần 2, vậy 3 đồng xu) và 4 (1 cần 1, vậy 2 đồng xu): tốt nhất là 2. Với 6, thử 1 (5 cần 2, vậy 3), 3 (3 cần 1, vậy 2) và 4 (2 cần 2, vậy 3): tốt nhất là 2, bằng 3 + 3. Tham lam thì đã trả 4 + 1 + 1.

Đếm số cách

Để đếm tổ hợp, hãy thêm các đồng xu lần lượt từng đồng một. Khi chỉ có đồng xu đầu tiên, mỗi số tiền hoặc tạo được theo một cách, hoặc không tạo được. Khi một đồng xu mới c được thêm vào, số cách tạo số tiền a là số cách cũ, không dùng c, cộng với số cách tạo a − c khi c lại được phép dùng, vì mỗi cách đó trở thành một cách tạo a khi thêm một đồng c nữa. Với các đồng xu 1, 2 và 5 có 4 cách tạo 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 và 1 + 1 + 1 + 1 + 1.

Khi nào tham lam là đủ

Một hệ tiền xu mà tham lam luôn cho số đồng xu ít nhất được gọi là chính tắc. Phần lớn các loại tiền hiện đại được thiết kế như vậy, và năm 1994 David Pearson đã mô tả một phép kiểm tra hệ tiền xu với số bước chỉ tăng theo đa thức của số đồng xu. Các đồng xu cũ của Anh không chính tắc: tham lam trả 48 penny bằng một đồng nửa crown, một shilling và một sixpence, trong khi hai đồng florin là đủ.

Tự khám phá

Mở ứng dụng, chuyển sang chế độ xem Bảng và nhấn Bước. Trong chế độ Ít xu nhất, ô màu cam là số tiền đang được tính và ô màu xanh lam là số tiền nhỏ hơn còn lại sau đồng xu; hàng bên dưới lưu đồng xu cuối cùng, và cuối cùng các đồng xu được đọc ngược dọc theo hàng đó. Chuyển sang Số cách và xem các giá trị tăng dần từng hàng khi mỗi đồng xu được thêm vào.

Câu hỏi thường gặp

Bài toán đổi tiền xu có phải là bài toán cái túi không?

Là họ hàng gần. Phiên bản ít xu nhất là một bài toán cái túi không giới hạn, trong đó mỗi đồng xu là một món đồ có trọng lượng bằng mệnh giá của nó, chiếc túi phải được lấp đầy chính xác, và mục tiêu là ít món đồ nhất.

Độ phức tạp thời gian là bao nhiêu?

O(k·A) với k loại đồng xu và số tiền A, ở cả hai phiên bản. Bảng cho ít xu nhất có A + 1 ô, còn bảng cho số cách có (k + 1)·(A + 1) ô, dù chỉ một hàng là đủ nếu các ô được cập nhật tại chỗ.

Vì sao phải đếm các đồng xu theo thứ tự cố định?

Nếu mỗi số tiền thử mọi đồng xu, 1 + 2 và 2 + 1 sẽ bị tính là hai cách. Thêm các đồng xu từng hàng một nghĩa là một tổ hợp luôn được xây dựng từ các đồng xu trước đó trước, nên mỗi tổ hợp được tính đúng một lần.

Có thể đọc ngược các đồng xu cho số cách không?

Không thể thành một đáp án duy nhất, vì có rất nhiều cách. Phiên bản ít xu nhất lưu đồng xu cuối cùng của mỗi số tiền, và như vậy là đủ để dựng lại một tổ hợp tốt nhất.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Thử đổi tiền xu