Thuật tham lam là gì? Là cách để lấy nhiều số lượng nhất bằng ít lượt lấy(bốc) nhất Nếu có 2 tờ 200.000 đồng và 500.000 đồng, bạn sẽ chọn cái nào? => Đương nhiên là tờ 500.000 đồng Vậy thì đó là ví dụ của tham lam và như có thể thấy nếu ta phát triển thêm như k lần lấy hoặc giới hạn số tiền thì nó sẽ trở thành 1 bài toán hay! Bài toán ví dụ: n = int(input()) m = int(input()) k = int(input())
Giả sử có n tờ 100.000 đồng, m tờ 200.000 thì số tiền lớn nhất nhận được sau k lần lấy là bao nhiều?
Tả giải như sau:
Kiểm tra, nhưng trước khi đó đặt biến tổng
tong = 0
Kiểm tra:
Nếu k >= m: tong = k * 200000
Ngược lại thì tong = m * 200000 + (k-m) * n * 100000
Như sau:
if k >= m: tong = k * 200000 else: tong = m * 200000 + (k-n) * 100000
In tổng để lấy số tiền lớn nhất
print(tong)
Bình luận
Duy nói siêu đúng +1 cho Duy(from fellow kid!!!)