uses crt;
var i,n,k,j,kt:longint; a,l:array[1..10000]of longint;
begin
clrscr;
write('N=');readln(n);
write('k=');readln(k);
for i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
end;
for i:=n downto 1 do
for j:=i to n do
if (abs(a[i]+l[j]-k)<abs(l[i]-k))and(a[i]+l[j]<=k) then l[i]:=l[j]+a[i];
for i:=1 to n do if l[i]=k then kt:=1;
if kt=0 then writeln('NO') else writeln('YES');
readln
end.
//////////////////////////////////////////////////////////////
Giải thích:
Bài này mình dùng quy hoạch động gần giống với bài chọn các phần tử tạo thành tổng lớn nhất
Nhưng bài này là mình quy về bài chọn các phần tử sao cho có tổng gần k nhất
Bài này thì không cần dãy t(vị trí) như những bài khác.
Làm xong phần quy hoạch động mình sẽ xét mem trong dãy L có phần tử nào bằng k không
Nếu có thì xuất YES ngược lại thì xuất NO.
Nếu bạn chưa hiểu phần nào hay chạy thấy text nào sai thì để lại bình luận nha!!!!
Đây là bảng phương án và một số text cho bạn tham khảo:
