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

Trong lập trình cũng như trong thực tế, chắc hẳn các bạn đều đã gặp những bài toán với yêu cầu tìm kết quả tốt nhất thỏa mãn một hoặc một số điều kiện nào đó. Sự thật là chúng ta gặp các bài toán này khá thường xuyên, thậm chí vô cùng thực tiễn, chẳng hạn như:

  • Tìm cách trả số tiền TTT với nnn tờ tiền có mệnh giá cho trước, sao cho số tờ tiền cần sử dụng là nhỏ nhất?
  • Trong các nhà máy sản xuất vỏ lon đồ uống, các nhà thiết kế luôn luôn tìm cách thiết kế sao cho diện tích toàn phần của vỏ lon là nhỏ nhất nhằm giảm thiểu chi phí nguyên liệu. Bài toán đặt ra là với thể tích cần thiết là V,V,V, làm sao để tạo ra vỏ lon hình trụ có diện tích toàn phần nhỏ nhất? .........

Có rất nhiều bài toán như vậy trong Tin học, và chúng được gọi là các bài toán tối ưu. Thông thường, người ta sẽ hay nghĩ đến phương pháp Quy hoạch động khi giải các bài toán tối ưu, tuy nhiên, phương pháp này chỉ có thể áp dụng nếu như bài toán đang xét có bản chất đệ quy mà thôi. Thực tế có nhiều bài toán tối ưu không có thuật toán nào thực sự hữu hiệu để giải quyết, mà vẫn phải sử dụng mô hình xem xét tất cả các phương án rồi đánh giá chúng để chọn ra phương án tốt nhất.

Phương pháp Nhánh và Cận (Branch and Bound) chính là một phương pháp cải tiến từ phương pháp Quay lui, được sử dụng để tìm nghiệm của bài toán tối ưu.

2. Ý tưởng

Bước đầu tiên của phương pháp vẫn giống với ý tưởng của quay lui: Tìm cách biểu diễn nghiệm của bài toán dưới dạng một vector (x1,x2,…,xn),(x_1, x_2,\dots, x_n),(x1,x2,,xn), mỗi thành phần xix_ixi được chọn ra từ tập các ứng cử viên SiS_iSi.

Bước tiếp theo sẽ hơi khác một chút: Nếu như ở phương pháp Quay lui, chỉ cần tuần tự chọn các ứng cử viên cho từng thành phần của vector nghiệm, thì ở phương pháp Nhánh và cận, mỗi nghiệm X=(x1,x2,…,xn)X = (x_1, x_2, \dots, x_n)X=(x1,x2,,xn) của bài toán sẽ được đánh giá độ tốt bằng một hàm f(X)f(X)f(X). Vì đây là bài toán tối ưu, nên mục tiêu của chúng ta là đi tìm nghiệm có hàm f(X)f(X)f(X) tốt nhất, thường là lớn nhất hoặc nhỏ nhất.

Bước thứ 333 là xây dựng nghiệm của bài toán. Giả sử, các bạn đã xây dựng được iii thành phần của nghiệm là (x1,x2,…,xi)(x_1, x_2,\dots, x_i)(x1,x2,,xi) và chuẩn bị mở rộng nghiệm thành (x1,x2,…,xi,xi+1)(x_1, x_2,\dots, x_i, x_{i + 1})(x1,x2,,xi,xi+1). Nếu như bằng một cách nào đó, các bạn đánh giá được độ tốt của toàn bộ các nghiệm mở rộng của nhánh này là (x1,x2,…,xi,xi+1,… )(x_1, x_2,\dots, x_{i}, x_{i + 1},\dots)(x1,x2,,xi,xi+1,) và biết rằng không có nghiệm nào trong nhánh này "tốt hơn" nghiệm tốt nhất tại thời điểm đó, thì việc mở rộng tiếp từ (x1,x2,…,xi)(x_1, x_2,\dots, x_i)(x1,x2,,xi) sẽ là không cần thiết nữa, mà thay vào đó ta sẽ chuyển qua chọn ứng cử viên tiếp theo cho thành phần xix_ixi luôn.

Bằng phương pháp trên, ta sẽ loại bỏ được những nhánh không cần thiết để không duyệt vào các phương án đó, từ đó việc tìm ra nghiệm tối ưu sẽ nhanh hơn. Tuy nhiên, việc đánh giá được "độ tốt" của các nghiệm mở rộng không phải việc đơn giản, nhưng nếu làm được như vậy thì giải thuật sẽ thực thi nhanh hơn nhiều so với quay lui.

3. Lược đồ giải thuật

Để thực hiện giải thuật Nhánh và Cận, các bạn có thể sử dụng một hàm đệ quy giống như giải thuật Quay lui, nhưng thêm phần đánh giá nghiệm trước khi xây dựng thành phần thứ iii. Ngoài ra, ta cần sử dụng thêm một biến \text{best_solution} để ghi nhận nghiệm tốt nhất hiện tại.

Dưới đây là mô hình cài đặt bằng C++:

void branch_and_bound(i)
{
    // Đánh giá các nghiệm mở rộng
    if ({Các_nghiệm_mở_rộng_đều_không_tốt_hơn_best_solution})
        return;
	
    for (value in S[i])
    {
        x[i] = value; // Ghi nhận thành phần thứ i.
		
        if ({Tìm_thấy_nghiệm})
            best_solution = X; // Cập nhật lại best_solution bằng nghiệm vừa tìm được.
        else 
            branch_and_bound(i + 1); // Chưa tìm thấy nghiệm thì xây dựng tiếp.
		
        {Loại_bỏ_thành_phần_thứ_i}
    }
}

Bây giờ, hãy cùng đến với một số bài toán minh họa để hiểu rõ hơn về phương pháp!

II. Một số bài toán minh họa

1. Rút tiền ATM

Đề bài

Một máy ATM hiện có nnn tờ tiền có giá trị lần lượt là t1,t2,…,tnt_1, t_2,\dots, t_nt1,t2,,tn. Hãy tìm ra cách trả số tiền SSS sao cho số tờ tiền phải sử dụng là ít nhất?

Input:

  • Dòng đầu tiên chứa hai số nguyên dương nnn và S (1≤n≤20;1≤S≤1000)S \ (1 \le n \le 20; 1 \le S \le 1000)S (1n20;1S1000).
  • Dòng thứ hai chứa nnn số nguyên dương t1,t2,…,tnt_1, t_2,\dots, t_nt1,t2,,tn phân tách nhau bởi dấu cách (1≤ti≤1000;∀i:1≤i≤n)(1 \le t_i \le 1000; \forall i: 1 \le i \le n)(1ti1000;i:1in).

Output:

  • Nếu như có thể trả số tiền SSS thì in ra số tờ tiền ít nhất cần sử dụng và các tờ tiền được chọn, ngược lại in ra −1-11.

Sample Input:

10 390
200 10 20 20 50 50 50 50 100 100

Sample Output:

5
20 20 50 100 200

Phân tích ý tưởng

Nghiệm của bài toán có thể biểu diễn dưới dạng một vector gồm toàn các bit nhị phân 0−10 - 101 là x1,x2,…,xnx_1, x_2,\dots, x_nx1,x2,,xn với ý nghĩa: xi=0x_i = 0xi=0 là tờ tiền thứ iii không được chọn, xi=1x_i = 1xi=1 là tờ tiền thứ iii được chọn.

Mục tiêu chúng ta đang cần tìm một bộ nghiệm sao cho:

{t1×x1+t2×x2+⋯+tn×xn=S.(x1+x2+⋯+xn) MIN.\begin{cases}t_1 \times x_1 + t_2 \times x_2 + \cdots + t_n \times x_n = S.\\ (x_1 + x_2 + \cdots + x_n) \text{ MIN}. \end{cases}{t1×x1+t2×x2++tn×xn=S.(x1+x2++xn) MIN.

Giả sử các bạn đã xây dựng được iii thành phần của nghiệm là (x1,x2,…,xi),(x_1, x_2, \dots, x_i),(x1,x2,,xi), tổng số tờ tiền đã sử dụng là cntcntcnt và số tiền đã trả được là sum,sum,sum, thì ta nhận xét thấy:

  • Số tiền còn lại cần trả là S−sumS - sumSsum.
  • Nếu gọi tmax[i+1]t_{max}[i + 1]tmax[i+1] là giá trị của tờ tiền lớn nhất trong các tờ tiền còn lại (tmax[i+1]=max(ti+1,ti+2,…,tn)),(t_{max}[i + 1] = \text{max}\big(t_{i + 1}, t_{i + 2}, \dots, t_n)\big),