Cần giúp đỡ hướng đi bài toán đổi tiền

Chào mọi người.
Tình hình là là mình chọn bài này để làm đồ án:

Một quầy trả tiền có N loại tiền với các mệnh giá (giá trị tiền ghi trên tờ tiền ) là A[1],
A[2], …A[N] ( Các A[i] là nguyên dương và khác nhau từng đôi). Giả thiết loại tiền
mệnh giá A[i] có B[i] tờ (1 ≤ i ≤N). Có M khách ( được đánh số hiệu từ 1 đến M ) cần lấy
tiền. Số tiền khách j cần lấy là K[j], K[j] nguyên dương, 1 ≤ j ≤M). Quy định rằng với
mỗi khách hoặc quầy từ chối chưa trả tiền hoặc quầy phải trả đúng số tiền mà khách cần
lấy.Dữ liệu vào được cho trong file văn bản có tên INP.TXT trong đó dòng đầu ghi giá trị
N (N≤ 10), dòng tiếp theo ghi các giá trị A[1], A[2], …A[N], dòng tiếp theo ghi các giá
trị B[1], B[2], …B[N], sau đó là dòng ghi giá trị M (M≤ 20), cuối cùng là dòng ghi các
giá trị K[1], K[2], …K[M], tất cả các giá trị đều nguyên dương.

1. Đọc file dữ liệu và đưa ra màn hình nội dung file dữ liệu ( theo thứ tự trên).
2. Tìm cách trả tiền sao cho trả được nhiều khách nhất. Thông báo kết quả ra file
   văn bản với tên OUT2.TXT trong đó dòng đầu ghi số khách được trả tiền, trong các dòng
   tiếp theo, mỗi dòng ghi thông tin về một khách được trả tiền gồm số hiệu của khách, số
   tiền phải trả và dãy các số X[1], X[2],…X[N], trong đó X[i] là số tờ của loại tiền mệnh
   giá A[i], 1 ≤ i ≤N, được trả cho khách.
3. Tìm cách trả tiền sao cho trả được nhiều tiền nhất. Thông báo kết quả ra file văn
   bản với tên OUT3.TXT trong đó dòng đầu ghi tổng số tiền đã trả được, trong các dòng
   tiếp theo, mỗi dòng ghi thông tin về một khách được trả tiền theo quy cách giống câu 2
   Chú ý: Hai giá trị liền nhau trên một dòng của các file văn bản cách nhau ít nhất một dấu
   trắng.

2 bài này mình dùng tham lam nhưng làm ra ví dụ thì có trường hợp sai mất rồi. Còn có cách giải nào khác ko?