Fri Jan 27, 2012 4:46 pm
anh thy Đề: Cho số tự nhiên N và dãy gồm N số nguyên a[1],a[2],….,a[n].Cho số nguyên S>=o.Tìm dãy con dài nhất trong dãy trên sao cho tổng của các phần tử trong dãy con dãy con này <=S.
Dữ liệu vào: TONG.INP
Dòng 1: ghi số n,s
Dòng 2:ghi N số a[1],a[2],…,a[n]
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 phần tử trong dãy con dài nhất có tổng <=S
*Phân tích:
Gọi L[i,j] là độ dài của dãy con dài nhất
Khi xét phần tử từ ví trí 1 đến I mà có Z các phần tử trong dãy con <=j
-BCS:
Nếu i=0 (dãy a không có phần tử nào) nên L[0,j]=0 với mọi j=0,S
Nếu dãy a có 1 phần tử nên i=1
Nếu a[i]<=j thì L[1,j]=1
Nếu a[i]>j thì L[1,j]=0
-Xây dựng bảng:Tính L[i,j] với mọi i=2,n;với mọi j=0,S;
* Chọn số thứ I vào dãy con:
L[i,j]=L[i-1,j-a[i]]
*không chọn số thứ i:
L[i,j]=L[i-1,j]
-Truy vết:
Kết dòng i: L[N,S]
I=N;j=S;
Chừng nào còn số trong dãy làm
Begin
Nếu L[i,j]=L[i-1,j] thì không chọn số
Ngược lại
+chọn số i
+ tổng còn lại
+giảm i
Ví dụ:
TONG.INP
5 10
3 4 7 1 8
TONG.OUT
3
3 4 1
BẢNG
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 2 2 2 2
0 0 0 1 1 1 1 2 2 2 2
0 1 1 1 2 2 2 2 3 3 3
0 1 1 1 2 2 2 2 3 3 3
CHƯƠNG TRÌNH:
program tong;
const fi='TONG.INP';fo='TONG.OUT';
var N,S,i,j:integer;f:text;
L:array[0..100,0..100] of integer;
A:array[1..100] of integer;
DD:array[1..100] of boolean;
procedure doc;
begin
assign(f,fi);reset(f);
readln(f,N,S);
for i:=1 to N do read(f,a[i]);
close(f);
assign(f,fo);rewrite(f);
end;
procedure khoitao;
begin
Fillchar(l,sizeof(l),0);
For j:=0 to s2 do
If a[1]<=j then
[1,j]:=1
else
l[1,j]:=0;
end;
procedure xdbang;
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 truyvet;
begin
writeln(f,L[n,s]);
i:=n; j:=s;
while i>0 do
begin
if L[i,j]=L[i-1,j] then dec(i)
else
begin
dd[i]:=true;j:=j-a[i];
dec(i);
end;
for i:=1 to N do
if dd[i]=true then write(f,a[i],' ');
end;
end;
BEGIN
Fillchar(dd,sizeof(dd),false);
doc;khoitao;xdbang;truyvet;
END.
Bài trên làm sai rồi bạn tải bài của mình về tham khảo đi Link nè : [You must be registered and logged in to see this link.]
Dữ liệu vào: TONG.INP
Dòng 1: ghi số n,s
Dòng 2:ghi N số a[1],a[2],…,a[n]
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 phần tử trong dãy con dài nhất có tổng <=S
*Phân tích:
Gọi L[i,j] là độ dài của dãy con dài nhất
Khi xét phần tử từ ví trí 1 đến I mà có Z các phần tử trong dãy con <=j
-BCS:
Nếu i=0 (dãy a không có phần tử nào) nên L[0,j]=0 với mọi j=0,S
Nếu dãy a có 1 phần tử nên i=1
Nếu a[i]<=j thì L[1,j]=1
Nếu a[i]>j thì L[1,j]=0
-Xây dựng bảng:Tính L[i,j] với mọi i=2,n;với mọi j=0,S;
* Chọn số thứ I vào dãy con:
L[i,j]=L[i-1,j-a[i]]
*không chọn số thứ i:
L[i,j]=L[i-1,j]
-Truy vết:
Kết dòng i: L[N,S]
I=N;j=S;
Chừng nào còn số trong dãy làm
Begin
Nếu L[i,j]=L[i-1,j] thì không chọn số
Ngược lại
+chọn số i
+ tổng còn lại
+giảm i
Ví dụ:
TONG.INP
5 10
3 4 7 1 8
TONG.OUT
3
3 4 1
BẢNG
0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 2 2 2 2
0 0 0 1 1 1 1 2 2 2 2
0 1 1 1 2 2 2 2 3 3 3
0 1 1 1 2 2 2 2 3 3 3
CHƯƠNG TRÌNH:
program tong;
const fi='TONG.INP';fo='TONG.OUT';
var N,S,i,j:integer;f:text;
L:array[0..100,0..100] of integer;
A:array[1..100] of integer;
DD:array[1..100] of boolean;
procedure doc;
begin
assign(f,fi);reset(f);
readln(f,N,S);
for i:=1 to N do read(f,a[i]);
close(f);
assign(f,fo);rewrite(f);
end;
procedure khoitao;
begin
Fillchar(l,sizeof(l),0);
For j:=0 to s2 do
If a[1]<=j then
[1,j]:=1
else
l[1,j]:=0;
end;
procedure xdbang;
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 truyvet;
begin
writeln(f,L[n,s]);
i:=n; j:=s;
while i>0 do
begin
if L[i,j]=L[i-1,j] then dec(i)
else
begin
dd[i]:=true;j:=j-a[i];
dec(i);
end;
for i:=1 to N do
if dd[i]=true then write(f,a[i],' ');
end;
end;
BEGIN
Fillchar(dd,sizeof(dd),false);
doc;khoitao;xdbang;truyvet;
END.
Bài trên làm sai rồi bạn tải bài của mình về tham khảo đi Link nè : [You must be registered and logged in to see this link.]