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ư:
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ưởngBướ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++:
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! 1. Rút tiền ATMĐề bàiMộ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:
Output:
Sample Input:
Sample Output:
Phân tích ý tưởngNghiệ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 - 10−1 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:
|