program ex68;
var v,n,i,j,k:integer;
f0,f1:array[0..200]of boolean;
x:array[0..200]of integer;
begin
readln(v);
readln(n);
for i:=1 to n do readln(x[i]);
fillchar(f0,sizeof(f0),0);
f0[0]:=true;
for i:=1 to n do
begin
f1:=f0;
if x[i]>v then continue;
for j:=x[i] to v do
if f0[j-x[i]] then f1[j]:=true;
f0:=f1;
end;
for k:=v downto 0 do
if f1[k] then
begin
writeln(v-k); halt;
end;
end.
1 条评论
-
hahayang LV 10 @ 2016-11-13 15:38:11
背包型DP。
var
w:array[1..30] of longint;
f:array[0..20000] of longint;
n, m, i, j:longint;
begin
readln(m);
readln(n);
for i:=1 to n do readln(w[i]);
fillchar(f, sizeof(f), 0);
for i:=1 to n do
for j:=m downto w[i] do if f[j-w[i]]+w[i]>f[j] then f[j]:=f[j-w[i]]+w[i];
write(m-f[m])
end.
- 1
