Cho N đồng xu và giá tiền của mỗi đồng (V0,V1,…,VN−1 ), và số S . Tìm số đồng xu nhỏ nhất để tổng giá trị của chúng bằng S (số lượng đồng xu không giới hạn).

Để tìm số đồng xu nhỏ nhất để tổng giá trị của chúng bằng S, ta có thể sử dụng thuật toán Greedy. Bước thực hiện như sau: 1. Khởi tạo biến count = 0 (đếm số đồng xu đã sử dụng). 2. Sắp xếp mảng giá tiền của các đồng xu theo thứ tự tăng dần. 3. Lặp qua từng đồng xu từ lớn đến nhỏ: - Nếu giá trị của đồng xu lớn hơn S, bỏ qua đồng xu này và chuyển sang đồng xu nhỏ hơn. - Nếu giá trị của đồng xu nhỏ hơn hoặc bằng S, thực hiện các bước sau: + Tăng biến count lên 1. + Giảm giá trị S đi giá trị của đồng xu hiện tại. + Quay lại bước 3 để kiểm tra tiếp các đồng xu còn lại. Sau khi kết thúc vòng lặp, biến count sẽ chứa số đồng xu nhỏ nhất để tổng giá trị của chúng bằng S.