1. Bài toán trả tiền của máy rút tiền tự động ATM.

Trong máy rút tiền tự động ATM, ngân hàng đã chuẩn bị sẵn các loại tiền có mệnh giá 100.000 đồng, 50.000 đồng, 20.000 đồng và 10.000 đồng. Giả sử mỗi loại tiền đều có số lượng không hạn chế. Khi có một khách hàng cần rút một số tiền n đồng (tính chẵn đến 10.000 đồng, tức là n chia hết cho 10.000). Hãy tìm một phương án trả tiền sao cho trả đủ n đồng và số tờ giấy bạc phải trả là ít nhất.

Giải:

Gọi X = (X₁, X₂, X₃, X₄) là một phương án trả tiền, trong đó X₁ là số tờ giấy bạc mệnh giá 100.000 đồng, X₂ là số tờ giấy bạc mệnh giá 50.000 đồng, X₃ là số tờ giấy bạc mệnh giá 20.000 đồng và X₄ là số tờ giấy bạc mệnh giá 10.000 đồng.

Theo yêu cầu ta phải có X₁ + X₂ + X₃ + X₄ nhỏ nhất và

X₁ * 100.000 + X₂ * 50.000 + X₃ * 20.000 + X₄ * 10.000 = n.

Áp dụng kỹ thuật tham ăn để giải bài toán này là: để có tổng số tờ giấy bạc phải trả (X₁ + X₂ + X₃ + X₄) nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải được chọn nhiều nhất.

Trước hết ta chọn tối đa các tờ giấy bạc mệnh giá 100.000 đồng, nghĩa là X₁ là số nguyên lớn nhất sao cho X₁ * 100.000 £ n. Tức là X₁ = n DIV 100.000.

Xác định số tiền cần rút còn lại là hiệu n – X1 * 100000 và chuyển sang chọn loại giấy bạc 50.000 đồng, và cứ tiếp tục như thế cho các loại mệnh giá khác

2. Ví dụ

Khách hàng cần rút 1.290.000 đồng (n = 1290000), phương án trả tiền như sau:

X₁ = 1290000 DIV 100000 = 12.

Số tiền cần rút còn lại là 1290000 – 12 * 100000 = 90000.

X₂ = 90000 DIV 50000 = 1.

Số tiền cần rút còn lại là 90000 – 1 * 50000 = 40000.

X₃ = 40000 DIV 20000 = 2.

Số tiền cần rút còn lại là 40000 – 2 * 20000 = 0.

X₄ = 0 DIV 10000 = 0.

Ta có X = (12, 1, 2, 0), tức là máy ATM sẽ trả cho khách hàng 12 tờ 100.000 đồng, 1 tờ 50.000 đồng và 2 tờ 20.000 đồng.