uses math;
var
n,m,i,j,k:longint;
w,c:array[1..1000]of longint;
f:array[0..100,0..1000]of longint;
begin
readln(n,m);
for i:=1 to m do
readln(w[i],c[i]);
for i:=1 to m do
for j:=1 to n do
if j>=w[i] then
f[i,j]:=max(f[i-1,j],f[i-1,j-w[i]]+c[i])
else f[i,j]:=f[i-1,j];
writeln(f[m,n]);
end.

鄙视贴代码。

来个短的
var
i,j,t,m,c,v:integer;
f:array[0..1000]of integer;

function max(a,b:integer):integer;
begin
if a>b then exit(a) else exit(b);
end;

begin
fillchar(f,sizeof(f),0);
readln(t,m);
for i:=1 to m do begin
readln(c,v);
for j:=t downto c do f[j]:=max(f[j],f[j-c]+v)
end;
writeln(f[t]);
end.

0秒水过，鄙视那些只贴结果的人。
这是入门级动归
01背包问题
用一维数组逆向推就可以了
附上我丑陋的程序。。。
program medcine;
var value:array[0..1200] of longint;
t,i,j,m,a,b,max:longint;
begin
readln(t,m);
for i:=1 to t do value[i]:=-1;
for i:=1 to m do
begin
readln(a,b);
for j:=t downto 0 do
if value[j]>=0 then
if value[j]+b>value[j+a] then value[j+a]:=value[j]+b;
end;
max:=-1;
for i:=t downto 0 do
if value[i]>max then max:=value[i];
writeln(max);
end.

f=[0]*1001
v=[0]*101
a=[0]*101
x,y=raw_input().split(" ")
t=int(x);n=int(y)
for i in range(1,n+1):
x,y=raw_input().split(" ")
a[i]=int(x);v[i]=int(y);

for i in range(1,n+1):
for j in range(t,0,-1):
if j>=a[i]:
f[j]=max(f[j],f[j-a[i]]+v[i])

print f[t]

#include<iostream>
using namespace std;
int f[1002],c[102],w[102],n,v,i,j;
int main()
{
cin>>v>>n;
for(i=1;i<=n;++i) cin>>c[i]>>w[i];
for(i=1;i<=n;i++) for(j=v;j>=c[i];--j) f[j]=max(f[j],f[j-c[i]]+w[i]);
cout<<f[v]<<endl;
return 0;
}

测试数据 #0: Accepted, time = 193 ms, mem = 640 KiB, score = 10

测试数据 #1: Accepted, time = 12 ms, mem = 640 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 640 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 640 KiB, score = 10

测试数据 #4: Accepted, time = 12 ms, mem = 640 KiB, score = 10

测试数据 #5: Accepted, time = 127 ms, mem = 640 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 640 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 640 KiB, score = 10

Accepted, time = 389 ms, mem = 640 KiB, score = 100

#include<iostream>
using namespace std;
int f[1002],c[102],w[102],n,v,i,j;
int main()
{
cin>>v>>n;
for(i=1;i<=n;++i)
cin>>c[i]>>w[i];
for(i=1;i<=n;i++)
for(j=v;j>=c[i];--j)
f[j]=max(f[j],f[j-c[i]]+w[i]);
cout<<f[v]<<endl;
return 0;
}

纪念水题...

├ 测试数据 01：答案正确... (63ms, 4332KB)

├ 测试数据 02：答案正确... (0ms, 4332KB)

├ 测试数据 03：答案正确... (47ms, 4328KB)

├ 测试数据 04：答案正确... (47ms, 4332KB)

├ 测试数据 05：答案正确... (16ms, 4332KB)

├ 测试数据 06：答案正确... (0ms, 4332KB)

├ 测试数据 07：答案正确... (31ms, 4332KB)

├ 测试数据 08：答案正确... (31ms, 4332KB)

├ 测试数据 09：答案正确... (47ms, 4332KB)

├ 测试数据 10：答案正确... (47ms, 4332KB)

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

Accepted / 100 / 333ms / 4332KB

二维数组不会爆，没必要优化此题

AC不解释

一颗星纪念给了这么个水题- -

点击查看代码

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

程序代码：

var

time,value:array[1..100] of integer;

f:array[0..1001] of integer;

t,m,i,j:integer;

function max(x,y:integer):integer;

begin

if x>y then max:=x

else max:=y;

end;

begin

readln(t,m);

for i:=1 to m do

readln(time[i],value[i]);

for i:=1 to m do

for j:=t downto 1 do

if j-time[i]>=0 then

f[j]:=max(f[j],f[j-time[i]]+value[i]);

write(f[t]);

end.

01背包

水题

#include

using namespace std;

int main()

{

int m,n,t[101],v[101],j,i,f[101][1001]={0};//f[i][j]

cin>>n>>m;

for(i=1;i>t[i]>>v[i];

for(i=1;if[j])

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

else

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

}

cout

小小的留个名字....

var

t,m,i,j:integer;

yt:array[1..100] of integer;

v:array[1..100] of integer;

f:array[0..1000,0..1000] of integer;

function max(a,b:integer):integer;

begin

if a>b then max:=a

else max:=b;

end;

begin

readLn(t,m);

for i:=1 to m do readLn(yt[i],v[i]);

for i:=1 to m do

for j:=1 to t do begin

if j>=yt[i] then

f:=max(f,f+v[i])

else f:=f;

end;

write(f[m,t]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program t;

var t,m,i: integer;

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

begin

read(t,m);

for i:=1 to m do

read(b[i],p[i]);

for i:=1 to m do

for j:=t downto b[i] do

if a[j]

正宗的01背包……

var

t,m,i,j:longint;

v,w:array[1..100] of longint;

f:array[0..1000] of longint;

begin

readln(t,m);

for i:=1 to m do readln(v[i],w[i]);

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

for i:=1 to m do

for j:=t downto v[i] do

if f[j-v[i]]+w[i]>f[j]

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

writeln(f[t]);

end

var

i,j,k,t1,m,p:integer;

t,w:array[0..1011] of integer;

f:array[0..1011,0..1011] of integer;

function max(x,y:integer):integer;

var iii:integer;

begin

　　if x>y then max:=x

　　 else max:=y;

end;

begin

readln(t1,m);

for i:=1 to m do

　　begin

　　 readln(t[i],w[i]);

　　end;

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

for i:=1 to m do

　　for j:=1 to t1 do

　　 begin

　　　　if j>=t[i] then f:=max(f+w[i],f)

　　　　 else f:=f;

　　 end;

　　writeln(f[m,t1]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

正宗0-1背包问题

#include

using namespace std;

const int N=1001;

int f[N];

int a[N],w[N];

int t,n;

int init()

{

cin>>t>>n;

for (int i=1;i>w[i]>>a[i];

for (int i=1;i=w[i];j--)

f[j]=max(f[j],f[j-w[i]]+a[i]);

cout