Pascal:
Cho dãy số nguyên dương A[1], A[2], … A[n] và số nguyên dương P. Hãy chọn một số các số trong dãy sao cho tổng của các số được chọn lớn nhất và không vượt quá P
Dữ liệu vào: tệp văn bản VD1.INP gồm:
+Dòng đầu ghi hai số nguyên dương n và P (2<=n<=20 và P<=1000)
+Dòng thứ hai ghi n số trong dãy A, giữa các số cách nhau một dấu cách và có giá trị không vượt quá 100.
Kết quả: Ghi ra tệp văn bản VD1.OUT gồm:
+Dòng đầu ghi tổng các số được chọn.
+Dòng thứ hai ghi chỉ số các số được chọn.
Ví dụ
Input:
10 16
1 4 7 6 5 3 9 10 2 4
Output:
16
8 9 10
const fi=’tongp.inp’;
fo=’tongp.out’;
var a,x,b:array[1..100000] of longint;
n,p,i,max,t:longint;
f:text;
procedure ghinghiem;
var j:longint;
begin
t:=0;
for j:=1 to n do
if x[j]>0 then t:=t+a[j];
if (t>=max) and (t<=p) then
begin
max:=t;
move(x,b,sizeof(x));
end;
end;
procedure chay(i:longint);
var j:integer;
begin
for j:=1 downto 0 do
begin
x[i]:=j;
if i=n then ghinghiem
else chay(i+1);
end;
end;
begin
assign(f,fi);reset(f);readln(f,n,p);
for i:=1 to n do read(f,a[i]);close(f);
assign(f,fo);rewrite(f);
max:=0;
chay(1);
writeln(f,max);
for i:=1 to n do
if b[i]=1 then write(f,i,’ ‘);
close(f);
end.