Đổi tiền

Đổi tiền
Ở đất nước Omega người ta chỉ tiêu tiền xu. Có N loại tiền xu, loại thứ i có mệnh giá là ai đồng. Một người khách du lịch đến Omega du lịch với số tiền M đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.
Hướng dẫn:

Bài toán này khá giống bài toán xếp balô (“khối lượng” là mệnh giá, “giá trị” là 1), chỉ có một số thay đổi nhỏ: số đồng xu mỗi loại được chọn tuỳ ý (trong bài toán xếp balô mỗi đồ vật chỉ được chọn 1 lần) và tổng giá trị yêu cầu là nhỏ nhất.
Do đó ta cũng xây dựng hàm QHĐ một cách tương tự: Gọi L(i,t) là số đồng xu ít nhất nếu đổi t đồng ra i loại tiền xu (từ 1 đến i). Công thức tính L(i,t) như sau:
• L(i,0)=0;
• L(0,t)= ∞ với t>0.
• L(i,t)=L(i–1,t) nếu t<ai.
• L(i,t)=min(L(i–1,t), L(i,t–ai)+1) nếu t ≥ai.
Công thức này khác công thức của bài xếp balô ở chỗ: dùng hàm min chứ không phải hàm max (vì cần tìm cách chọn ít hơn) và nếu chọn đồng xu thứ i thì L(i,t)=L(i,t–ai)+1 (vì ta vẫn còn được chọn đồng xu thứ i đó nữa), khác với khi xếp balô là: nếu chọn đồ vật thứ i thì L(i,t)=L(i–1,t–ai) + bi vì đồ vật i chỉ được chọn một lần.