[pascal] Toán đổi tiền

[rabbit.thuy]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Bài tập này có dạng tương tự bài đổi tiền.
Cho số nguyên dương S và tập A gồm N số nguyên dương a1...aN, đôi 1 khác nhau và a1=1. Biết S có thể viết thành tổng các fần tử trong A.
Yêu cầu: tìm tổng các fần tử trong A bằng S mà chứa ít số hạng nhất, sau đó in ra các fần tử đó.
vd:
Sum.inp:
S=14 N=6
dãy A:
1 2 3 5 7 10
Sum.out:
2(số fần tử)
14=7+7
Bài này mình đã tìm được số lượng fần tử là 2 bằng fương fáp quy hoạch động
f[0]=0; full f[]=maxint;
For i:=1 to s do
for j:=1 to n do if i>a[j] then if f>=f[i-a[j]]+1 then f:=f[i-a[j]]+1;
Có đc f. Mình gặp vấn đề ở chỗ truy vết tìm ra 7. Mong mọi ng` giúp đỡ.

 

[rabbit.thuy]

Thành thật xin lỗi mọi người. Vừa post bài xong thì nghĩ ra đc phương án. Thôi coi như để mọi người tham khảo vậy

 

[hung1xpro96]

phương án sao vậy bạn ? có thể nói ra được không ?

 

[rabbit.thuy]

Truy vết bằng cách sử dụng 1 biến b lưu chỉ số j nếu thỏa mãn điều kiện. Kết thúc vòng lặp trên, b sẽ lưu vị trí phần tử cuối cùng trong mảng A thỏa mãn điều kiện (vd bài trên: b=5). Từ vị trí đó ta sẽ truy ngược về trước:

  k:=f[s]; h:=s;
        while k<>0 do
                begin
                        if h>=a[b] then begin write(f2,a[b],' ');
                                h:=h-a[b];
                                 dec(k);
                                 end;
                        if h<a[b] then dec(b);
                end;

Và mình cũng tìm ra đc cách in ra số lượng cách tối đa phân tích S thành tổng các phần tử of A. Ta sử dụng một mảng c lưu số cách phân tích i:

 for j:=1 to n do
                        if i>=a[j] then if f[i]>=f[i-a[j]]+1 then
                                begin
                                        f[i]:=f[i-a[j]]+1;
                                        c[i]:=c[i]+c[i-a[j]];
                                        b:=j;
                                end;

Kết quả in ra f là cách tối ưu, còn c là số cách tối đa có thể phân tích.

 

[asdads]

Bạn nào có thể giúp tớ bài này được không?Xin cảm ơn rất nhiều:
Một ngân hàng có N loại tiền mệnh giá A[1]..A[n] với số tiền không giới hạn cần tri trả cho khách 1 số tiền m đồng.
Tìm cách trả sao cho lượng tờ là ít nhất.
Dữ liệu vào từ fileOITIEN.INP
Nếu không có cách nào thì ghi :No Solution.
VD
DOITIEN.INP DOITIEN.OUT
3 12 3
4 10 3 3 0 0
Xin chân thành cảm ơn.