贴一个短点的..

var f:array[0..20000]of boolean;

i,n,maxv,v,j:longint;

begin

readln(maxv);

readln(n);

f[0]:=true;

for i:=1 to n do

begin

readln(v);

for j:=maxv downto v do if f[j-v] then f[j]:=true;

end;

for i:=maxv downto 1 do if f[i] then

begin

writeln(maxv-i);

halt;

end;

end.

program zhuang;

var

v,n,i,k:integer;

x:array[1..10000] of integer;

f0,f1:array[1..10000] of boolean;

begin

readln(v,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.

#include

using namespace std;

int sum=0,a[30000];

int n,v;

void work()

{

int i,j;

cin>>v>>n;

int maxn=0;

for (i=1;i>i1;

a[i1]=1;

maxn=max(maxn,i1);

int max1=maxn;

for (j=max1;j>=1;j--)

if (a[j]&&(j+i1=0;j--)

if (a[j])

{

cout

MS是最短的一个C++

#include

using namespace std;

int main(){

int m,n,tv,v,i,j,a[20001]={0};

a[0]=1;

cin >> v;

cin >> n;

for(i=0;i> tv;

for(j=v;j>=tv;j--){

if(a[j]==0){

a[j] = a[j-tv];

}

}

}

m = v;

while(a[m]==0) m--;

cout

so easy

Flag 　　 Accepted

题号 　　P1133

类型(?) 　　动态规划

通过 　　5895人

提交 　　14178次

通过率 　　42%

难度 　　2

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

０１背包

超短

秒杀

ＭＡＩＮ：

for i:=1to maxn do

for j:=maxw downto weight[i]do

if tot[j-weight[i]]+weight[i]>tot[j]

then tot[j]:=tot[j-weight[i]]+weight[i];

无语了……

var

m,n,i,j:longint;

v,f:array[0..20000] of longint;

begin

readln(m);

readln(n);

for i:=1 to n do readln(v[i]);

fillchar(f,sizeof(f),0);

f[0]:=1;

for i:=1 to n do

for j:=m downto v[i] do

f[j]:=f[j]+f[j-v[i]];

for i:= m downto 1 do

if f[i]>0 then

begin

writeln(m-i);

halt;

end;

writeln(m);

end.

program ws;

var a:array[1..30] of longint;

b:array[1..10000] of longint;

n,m,gd,i,j,o,k,s,min,f:longint;

begin

j:=0;

readln(n,m);

for i:=1 to m do

readln(a[i]);

for f:=0 to m do

begin

o:=f; k:=f; gd:=0;

while om do

begin

if k=0 then gd:=gd+0

else gd:=gd+a[k];

for i:=k+1 to m do

begin

j:=j+1;

b[j]:=b[j]+gd+a[i];

end;

if i=m then

begin

o:=o+1;

k:=o;

end;

end;

end;

min:=n-b[1];

min:=abs(min);

for i:=2 to j do

if (b[i]

#include "stdio.h"

#include "stdlib.h"

int main()

{

int n, v, i, j, used[20001], w[31], remain;

scanf("%d%d",&v,&n);

for(i=1;i=w[i]) && (used[j-w[i]]+w[i]>used[j]))

used[j]=used[j-w[i]]+w[i];

remain=(v-used[v]);

printf("%d",remain);

return 0;

}

为什么我第五个点不对呢？ 求教

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|

直接背包! 十分钟不到就Ac.

f[i][j] = f[j];

if( j >= a[i] && f[j-a[i]]+a[i] > f[i][j]){

f[i][j] = f[j-a[i]]+a[i];

}

楼下的楼下，to是完全BAG，downto是01BAG。

详见《背包九讲》

与P1104采药的题解差不多...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

H2O

不过有个疑问

为什么 to 是20分

downto 就A了？

Var

f:array [0..20000] of Boolean;

a:array [1..30] of Longint;

i,j,n,v:Longint;

Function max(a,b:Longint):Longint;

Begin

If a>b Then Exit(a) Else Exit(b);

End;

Begin

Readln(v,n);

For i:=1 to n Do Read(a[i]);

f[0]:=true;

For i:=1 to n Do

For j:=v downto a[i] Do If f[j-a[i]] Then f[j]:=true;｛介个地方｝

For i:=v downto 1 Do If f[i] Then Begin

Writeln(v-i);

Halt;

End;

End.

//P1133 装箱问题

#include

using namespace std;

int a[20001];

int main(){

int n,v,i,j,x;

cin>>v>>n;

a[0]=1;

for (i=1;i>x;

for (j=v-x;j>=0;j--){

if (a[j]){

a[j+x]=1;

}

}

}

for (i=v;i>=1;i--){

if (a[i])break;

}

cout

水题一道。

晾一下程序，51题AC。

program cl(input,output);

var f:array[0..20000]of boolean;

a:array[1..30]of longint;

v,n,i,j,ans:longint;

begin

readln(v);

readln(n);

for i:=1 to n do

read(a[i]);

f[0]:=true;

for i:=1 to n do

for j:=v downto a[i] do

if f[j-a[i]]=true then f[j]:=true;

for i:=v downto 1 do

begin

if f[i] then break;

inc(ans);

end;

writeln(ans);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：运行时错误...|错误号: 216

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：0ms

var f,q:array[0..10000] of longint;

n,m,i,j,k,a,b,c:longint;

begin

read(n,m);

for i:=1 to m do

readln(f[i]);

for i:=1 to m do

for j:=n downto 1 do

if f[i]q[j] then q[j]:=a;

end;

writeln(n-q[n]);

end.

那位仁兄帮我看看哪里错了

虽然简单，但却是基础，我认为dp方程还是有必要写一下的：

f[m,j]=min{f[m-v[j],j-1]+v[j],f[m,j-1]}

然后用一维的方法来实现就行了。

var

v,i,j,m,n:integer;

a,b:array[1..20000] of integer;

begin

readln(v);

readln(n);

for i:=1 to n do

readln(a[i]);

for i:= 1 to n do

for j:=v downto 1 do

if (a[i]b[j])then b[j]:=m;

end;

writeln(v-b[v]);

end.

var

w:array[0..20000]of integer;

f:array[1..30]of integer;

v,n,i,j,d:integer;

begin

read(v,n);

for i:=1 to n do read(f[i]);

for i:=1 to n do

for j:=v downto 1 do

if(f[i]w[j])then w[j]:=d;

end;

writeln(v-w[v]);

end.

典型用DP解背包的问题，大胆的用O(vn)的方法做。

标准0-1背包...