1/ Cho số tự nhiên n và dãy gồm n số nguyên a1,a2,...,an. Cho số nguyên S>=0 . Tìm dãy con dài nhất trong dãy sao cho tổng của p/tử trong dãy này <=S .


Dữ liệu vào : tong.inp
- Dòng 1 : Ghi số n ,s.
- Dòng 2 :ghi N số a1,a2,...,an.
Dữ liệu ra : tong.out
- Dòng 1 : Ghi độ dài dãy con dài nhất có tổng <= S
- Dòng 2 : Ghi các p/tử trong dãy con dài nhất có tổng <= S
Vd:
Tong.inp
5 10
3 4 7 1 8
Tong.out
3
3 4 1

Code:

Program Tong;
Const fi='tong.inp';fo='tong.out';
Var a:Array[1..100] Of Integer;
l:array[0..100,0..100] Of Integer;
chon:array[1..100] Of Boolean;
i,j,m,n,s:Byte;g,f:text;
Procedure doctep;
Begin
Assign(f,fi);
Reset(f);
Readln(f,n,s);
For i:=1 to n do
Read(f,a[i]);
Close(F);
End;
Procedure khoitao;
Begin
Fillchar(l,sizeof(l),0);
For j:=0 to s do
If a[1]<=j then
l[1,j]:=1
Else
l[1,j]:=0;
End;
Procedure xd;
Begin
For i:=2 to n do
For j:=1 to s do
Begin
l[i,j]:=l[i-1,j];
If j-a[i]>=0 then
If l[i,j]<(1+l[i-1,j-a[i]]) then
l[i,j]:=1+l[i-1,j-a[i]];
End;
End;
Procedure truy;
Begin
Assign(g,fo);
Rewrite(g);
WRiteln(g,l[n,s]:3);
i:=n;j:=s;
While i>0 do
Begin
If l[i,j]=l[i-1,j] then dec(i)
Else
If l[i,j]<>l[i-1,j] then
Begin
chon[i]:=true;
j:=j-a[i];
dec(i);
End;
End;
For i:=1 to n do
If chon[i]=true then
WRite(g,a[i]:3);
Close(G);
End;
Begin
doctep;
khoitao;
For i:=1 to n do
chon[i]:=false;
xd;
truy;
End.


Link tải bài giải về : [You must be registered and logged in to see this link.]