别问我为什么交这么多次，我就是想知道怎么弄才能弄成0ms。who can tell me？

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

呵呵？需要3个数组？？？醉了。把价值和容量存下来有用？？？

第一次写动态规划，虽然还是有点不懂，不过大致是明白一点倪端了~~

###block code
program P1104;
uses math;
var t,m,i,a,b,j:longint;
data:array[0..1000] of longint;
begin
read(t,m); fillchar(data,sizeof(data),0);
for i:=1 to m do
begin
read(a);read(b);
for j:=t downto a do
begin
data[j]:=max(data[j],data[j-a]+b);
end;
end;

write(data[t]);
end.

include<iostream>
include<algorithm>

using namespace s
td;

int t[110],v[110];
int f[10

10];
int main()
{
int T,m;
cin>>T>>m;
for (int i=1;i<=m;i++)
cin>>t[i]>>v[i];
for (int i=1;i<=m;i++)
for (int j=T;j>=0;j--)
if (j>=t[i])
f[j]=max(f[j-t[i]]+v[i],f[j]);
cout<<f[T]<<endl;
return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int t[110],v[110];
int f[1010];
int main()
{
int T,m;
cin>>T>>m;
for (int i=1;i<=m;i++)
cin>>t[i]>>v[i];
for (int i=1;i<=m;i++)
for (int j=T;j>=0;j--)
if (j>=t[i])
f[j]=max(f[j-t[i]]+v[i],f[j]);
cout<<f[T]<<endl;
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 892 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 892 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 888 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 892 KiB, score = 10
Accepted, time = 15 ms, mem = 892 KiB, score = 100
代码
uses math;
var
a,b,f:array[0..1000]of longint;
n,i,j,t:longint;
begin
read(t,n);
for i:=1 to n do
read(b[i],a[i]);
for i:=1 to n do
for j:=t downto b[i] do
f[j]:=max(f[j],f[j-b[i]]+a[i]);
write(f[t]);
end.

测试数据 #0: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 892 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 892 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 888 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 892 KiB, score = 10
Accepted, time = 15 ms, mem = 892 KiB, score = 100
代码
uses math;
var
a,b,f:array[0..1000]of longint;
n,i,j,t:longint;
begin
read(t,n);
for i:=1 to n do
read(b[i],a[i]);
for i:=1 to n do
for j:=t downto b[i] do
f[j]:=max(f[j],f[j-b[i]]+a[i]);
write(f[t]);
end.

#include<iostream>
using namespace std;
int t,m,f[10001][10001],w[101],c[101],i,v;
main()
{
cin>>t>>m;
for(i=1;i<=m;i++)
cin>>w[i]>>c[i];
for(i=1;i<=m;i++)
for(v=t;v>0;v--)
if(w[i]<=v)
f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
else
f[i][v]=f[i-1][v];
cout<<f[m][t];
}

很简单嘛
var n,c,i,j:longint;
w,v:array[1..1000]of integer;
f:array[0..1000,0..1000]of integer;
begin
read(c,n);
for i:=1 to n do read(w[i],v[i]);
for i:=0 to n do f[i,0]:=0;
for i:=0 to c do f[0,i]:=0;
for i:=1 to n do
for j:=0 to c do
if j>=w[i] then begin
if f[i-1,j-w[i]]+v[i]>f[i-1,j] then
f[i,j]:=f[i-1,j-w[i]]+v[i] else f[i,j]:=f[i-1,j];
end
else f[i,j]:=f[i-1,j];
write(f[n,c]);
end.

var
t,m,i,j:longint;
a,b,p:array[1..1000] of longint;
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]<a[j-b[i]]+p[i] then
a[j]:=a[j-b[i]]+p[i];
write(a[t]);
end.

测试数据 #0: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 12356 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 12356 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 12360 KiB, score = 10
Accepted, time = 0 ms, mem = 12360 KiB, score = 100

var
t,m,i,J: 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]<a[j-b[i]]+p[i]
then a[j]:=a[j-b[i]]+p[i];
write(a[t]);
end.
什么意思

有人说c++不能用memset，事实证明可以
#include<stdio.h>
#include<string.h>
#define maxn 100+10
#define maxm 1000+10
int t[maxn],v[maxn];
int f[maxn][maxm];

int max(int x,int y)
{
if (x>y) return x;
else return y;
}

int main()
{
memset(t,0,sizeof(t));
memset(v,0,sizeof(v));
memset(f,0,sizeof(f));
int tt,mm,i,j;
scanf("%d%d",&tt,&mm);
for (i=1;i<=mm;i++)
scanf("%d%d",&t[i],&v[i]);
for (j=t[1];j<=tt;j++)
f[1][j]=v[1];
for (i=2;i<=mm;i++)
for (j=0;j<=tt;j++)
{
if (j-t[i]>=0) f[i][j]=max(f[i-1][j],f[i-1][j-t[i]]+v[i]);
else f[i][j]=f[i-1][j];
}
printf("%d\n",f[mm][tt]);
return 0;
}

var
a:array[0..100,0..1000] of longint;
b,c:array[0..100] of longint;
i,j,k,l,q,w,e,n,m:longint;
function max(x,y:longint):longint;
begin
if x>y then
exit(x) else
exit(y);
end;
begin
readln(m,n);
for i:=1 to n do readln(b[i],c[i]);
for i:=1 to n do
for j:=0 to m do if j-b[i]<0 then a[i,j]:=a[i-1,j] else
a[i,j]:=max(a[i-1,j],a[i-1,j-b[i]]+c[i]);
writeln(a[n,m]);
end.

测试数据 #0: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 852 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 856 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 848 KiB, score = 10
Accepted, time = 15 ms, mem = 856 KiB, score = 100
代码
var
i,j,k,n,m,t:longint;
v,w,f:array[0..10000] of longint;

begin
readln(t,n);
for i:=1 to n do
read(w[i],v[i]);
for i:=1 to n do
for j:=t downto w[i] do
if f[j]<f[j-w[i]]+v[i] then f[j]:=f[j-w[i]]+v[i];
writeln(f[t]);
end.
和装箱那道没差多少

来个c++的
###
#include<cstdlib>
#include<cstdio>
#include<vector>
using namespace std;
const int maxsize=10005;
int t,m,no_use=0,maxvolue=0;
struct medicine
{
int v;int t;
};
vector<medicine>v;
int main()
{
scanf("%d %d\n",&t,&m);
for(int i=0;i<m;i++)
{
medicine tmp;
scanf("%d %d\n",&tmp.t,&tmp.v);
if(tmp.t<t)v.push_back(tmp);
else no_use++;
}
bool a[maxsize]={true};//if
//int b[71]={0};//time
int c[maxsize]={0};//volue
for(int i=0;i<m-no_use;i++)
{
for(int j=maxsize-1;j>=0;j--)
{
if(a[j]/*if*/&&j+v[i].t<=t/*time*/&&c[j+v[i].t]<=c[j]+v[i].v/*volue*/)
{
a[j+v[i].t]=true;/*if*/
/*time*/
c[j+v[i].t]=c[j]+v[i].v;/*volue*/
if(maxvolue<c[j+v[i].t])maxvolue=c[j+v[i].t];
else;
}
else;
}
}
printf("%d\n",maxvolue);
}

var k,v: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(k[i],v[i]);
for i:=1 to m do
for j:=t downto 1 do
if j-k[i]>=0 then f[j]:=max(f[j],f[j-k[i]]+v[i]);
write(f[t]);
end.

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

var a:array[0..100,0..1000] of longint;
b,c:array[0..100] of longint;
i,j,k,l,q,w,e,n,m:longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
begin
readln(m,n);
for i:=1 to n do readln(b[i],c[i]);
for i:=1 to n do
for j:=0 to m do if j-b[i]<0 then a[i,j]:=a[i-1,j] else
a[i,j]:=max(a[i-1,j],a[i-1,j-b[i]]+c[i]);
writeln(a[n,m]);
end.

当我uses了个math后，好心的360提醒我：这是个病毒，然后删掉了。
我擦^%&*\(***^#%%\)#@!@#