- 装箱问题
- 2017-03-29 17:51:12 @
Program box;
var
n,max,v:int64;
i,j:longint;
a,f:array[1..10000] of int64;
begin
readln(v);
readln(n);
for i:=1 to n do readln(a[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=v downto a[i] do
begin
if f[j-a[i]]+a[i]>f[i] then
f[i]:=f[j-a[i]]+a[i];
end;
max:=0;
for i:=1 to n do
if max<f[i] then
max:=f[i];
writeln(v-max);
end.
4 条评论
-
hahayang LV 10 @ 2017-04-02 16:51:34
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.
注意:
f数组范围是0~20000!!! -
2017-04-02 16:22:16@
转移方程好像错了,f[i,j]=max(f[i-1,j-a[i]]+a[i],f[i-1,j])
-
2017-03-29 18:06:43@
你这会访问
f[0]
吧。。
还有请善用这个按钮(注意要把C++改成Pascal)
当然还有和 -
2017-03-29 17:51:36@
到底怎么回事啊?
- 1