01/10/2018, 11:59
Cần giúp về thuật toán và chương trình đổi tiền lẻ
Bài toán:
Nhập từ bàn phím một n đô la (n>0). Hãy tìm ra cách đổi n đô la đó ra các loại tiền giấy (bills) và tiền xu (coins) có mệnh giá 1 cent, 5 cent, 25 cent, 50 cent, $1, $5, $10, $20, $50, $100 sao cho tổng các đồng tiền xu và tiền giấy đổi được là ít nhất có thể
Làm ơn giúp mình với, mình nghĩ hoài không ra. Yêu cầu đề bài là viết bằng C++ 2013, Win32 Console Application, không có giới hạn về bộ nhớ cũng như số câu lệnh
Bài liên quan
Cái này là quy hoạch động rồi.
Chia số tiền thành 2 phần: phần nguyên và phần lẻ. Làm bài toán đổi tiền trên 2 phần đó.
Bạn xem thuật toán ở đây:
Find minimum number of coins that make a given value - GeeksforGeeks
Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1,… Read More »
Coin Change | DP-7 - GeeksforGeeks
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1,… Read More »
Toàn 1 2 5 10 thì greed chắc cũng đúng.
Tham lam đến một lượng đủ nhỏ rồi Qui hoạch động lốt chỗ còn lại. Có 10 loại tiền QHĐ toàn bộ cũng vẫn ổn nhỉ :v