#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int n,v,w[101],p[101],f[101][1001];
scanf("%d%d",&n,&v);
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i],&w[i]);
int ans=-1;
f[0][0]=0;
for(int i=1;i<=v;i++)
f[0][i]=-1;
for(int i=1;i<=n;i++)
for(int j=0;j<=v;j++)
{
if(j-w[i]>=0)
{
int pd1=f[i-1][j];
int pd2=f[i-1][j-w[i]];
if(pd1!=-1&&pd2!=-1)
f[i][j]=max(pd1,pd2+p[i]);
else
if(pd1==-1&&pd2!=-1)
f[i][j]=pd2+p[i];
else
if(pd1!=-1&&pd2==-1)
f[i][j]=pd1;
else
f[i][j]=-1;
}
else
{
if(f[i-1][j]!=-1)
f[i][j]=f[i-1][j];
else
f[i][j]=-1;
}
if(i==n)
{
if(f[i][j]>ans)
ans=f[i][j];
}
}
printf("%d\n",ans);
return 0;
}

裸的背包问题
#include <cstdio>
#include <cstring>
#include <algorithm>
int main() {
int T,M,time[101],value[101];
int solution[1001][101];
scanf("%d%d",&T,&M);
for(int i=1;i<=M;i++) scanf("%d%d",&time[i],&value[i]);
memset(solution,0,sizeof(solution));
for(int i=1;i<=T;i++)
for(int j=1;j<=M;j++) {
if(time[j]>i) solution[i][j]=solution[i][j-1];
else solution[i][j]=std::max(solution[i][j-1],value[j]+solution[i-time[j]][j-1]);
}
printf("%d",solution[T][M]);
return 0;
}

编译成功

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

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

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

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

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

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

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

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

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

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

Accepted, time = 0 ms, mem = 5224 KiB, score = 100

简单的背包问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1100;
const int M = 150;
LL dp[N];
int pa[N][N];
int n,m,t;
LL num;
void add(int t,int v)
{
for(int i = n; i >= t; i--)
dp[i] = max(dp[i],dp[i-t]+v);
}
int main()
{
while(scanf("%d%d",&n,&m) == 2)
{
memset(dp,0,sizeof(dp));
int a,b;
for(int i = 0; i < m; i++)
{
scanf("%d%d",&a,&b);
add(a,b);
}
printf("%I64d",dp[n]);
}
}

var f:array[0..1001,0..1001] of integer;
w,v:array[1..5000] of integer;
t,m,i,j:integer;
begin
readln(t,m);
for i:=1 to m do read(w[i],v[i]);
for i:=1 to t do f[0,i]:=0;
for i:=1 to m do f[i,0]:=0;
for i:=1 to m do
for j:=1 to t do begin
f[i,j]:=f[i-1,j];
if j>=w[i] then
if f[i-1,j]<=f[i-1,j-w[i]]+v[i] then f[i,j]:=f[i-1,j-w[i]]+v[i];
end;
write(f[m,t]);
end.

program beibao01;
var
n,i,mz:longint;
m,v:array[0..100] of longint;

function dp(a,b:integer):longint;
var j:longint;
begin
if a=1 then
begin if b>=m[1] then dp:=v[1]
else dp:=0;
end

else
begin
if b>=m[a] then
begin if dp(a-1,b)>=dp(a-1,b-m[a])+v[a]
then dp:=dp(a-1,b)

else dp:=dp(a-1,b-m[a])+v[a] end
else dp:=dp(a-1,b)
end;
end;
begin
read(mz,n);
for i:=1 to n do readln(m[i],v[i]);

writeln(dp(n,mz));

end.

uses math;
var
n,m,v,i,mz,j:longint;

dp:array[0..100,0..1000] of longint;

begin
readln(mz,n);
for j:=1 to mz do dp[0,j]:=0;
for i:=1 to n do
begin
readln(m,v);
for j:=m to mz do dp[i,j]:=max(dp[i-1,j],dp[i-1,j-m]+v);
for j:=1 to m-1 do dp[i,j]:=dp[i-1,j];

end;
writeln(dp[n,mz]);
end.

uses math;
var
n,m,v,i,mz,j:longint;

dp:array[0..100,0..1000] of longint;

begin
readln(mz,n);
for j:=1 to mz do dp[0,j]:=0;
for i:=1 to n do
begin
readln(m,v);
for j:=m to mz do dp[i,j]:=max(dp[i-1,j],dp[i-1,j-m]+v);
for j:=1 to m-1 do dp[i,j]:=dp[i-1,j];

end;
writeln(dp[n,mz]);
end.

program beibao01;
var
n,i,mz:longint;
m,v:array[0..100] of longint;

function dp(a,b:integer):longint;
var j:longint;
begin
if a=1 then
begin if b>=m[1] then dp:=v[1]
else dp:=0;
end

else
begin
if b>=m[a] then
begin if dp(a-1,b)>=dp(a-1,b-m[a])+v[a]
then dp:=dp(a-1,b)

else dp:=dp(a-1,b-m[a])+v[a] end
else dp:=dp(a-1,b)
end;
end;
begin
read(mz,n);
for i:=1 to n do readln(m[i],v[i]);

writeln(dp(n,mz));

end.

uses math;
var
mz,j:1..1000;
n,m,v,i:1..100;
dp:array[0..100,0..1000] of longint;

begin
readln(mz,n);
for j:=1 to mz do dp[0,j]:=0;
for i:=1 to n do
begin
readln(m,v);
for j:=m to mz do dp[i,j]:=max(dp[i-1,j],dp[i-1,j-m]+v);
for j:=1 to m-1 do dp[i,j]:=dp[i-1,j];

end;
writeln(dp[n,mz]);
end.

program beibao01;
var
n,i,mz:longint;
m,v:array[0..100] of longint;

function dp(a,b:integer):longint;
var j:longint;
begin
if a=1 then
begin if b>=m[1] then dp:=v[1]
else dp:=0;
end

else
begin
if b>=m[a] then
begin if dp(a-1,b)>=dp(a-1,b-m[a])+v[a]
then dp:=dp(a-1,b)

else dp:=dp(a-1,b-m[a])+v[a] end
else dp:=dp(a-1,b)
end;
end;
begin
read(mz,n);
for i:=1 to n do readln(m[i],v[i]);

writeln(dp(n,mz));

end.

program beibao01;
var
n,i,mz:longint;
m,v:array[0..100] of longint;

function dp(a,b:integer):longint;
var j:longint;
begin
if a=1 then
begin if b>=m[1] then dp(1,b):=v[1]
else dp(1,b):=0;
end

else
begin
if b>=m[a] then
begin if dp(a-1,b)>=dp(a-1,b-m[a])+v[a]
then dp(a,b):=dp(a-1,b)

else dp(a,b):=dp(a-1,b-m[a])+v[a] end
else dp(a,b):=dp(a-1,b)
end;
end;
begin
read(mz,n);
for i:=1 to n do readln(m[i],v[i]);

writeln(dp(n,mz));

end.

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1000000;

int t[MAXN],v[MAXN],f[MAXN];

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>=t[i]; j--)
f[j] = max(f[j],f[j-t[i]]+v[i]);
cout<<f[T];

system("pause");
return 0;
}

var
a,b,f:array[0..1000]of longint;
n,i,j,t:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
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.

第一道自主完成的DP题目...

#include<stdio.h>
int main( )
{
int t,m,t1[101],p1[101],ans[1001]={0};
int i,j,k;

scanf("%d %d",&t,&m);

for(i=1;i<=m;i++)
scanf("%d %d",&t1[i],&p1[i]);

for(i=1;i<=m;i++)
for(j=t;j>=t1[i];j--)
if(ans[j-t1[i]]+p1[i]>ans[j]) ans[j]=ans[j-t1[i]]+p1[i];

printf("%d",ans[t]);

return 0;

}

/*************************************************************************
> File Name: 1104.cpp
> Author: Netcan
> Blog: http://www.netcan.xyz
> Mail: 1469709759@qq.com
> Created Time: Fri 01 May 2015 20:15:19 CST
************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
using namespace std;

int main()
{
int T, M;
int t[105];
int v[105];
int dp[105][1005];
while(scanf("%d%d", &T, &M) == 2) {
for(int i=1; i<=M; ++i)
scanf("%d%d", &t[i], &v[i]);
memset(dp, 0, sizeof(dp));
for(int i=1;i<=M; ++i)
for(int j=0; j<=T; ++j) {
if(j-t[i]>=0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]]+v[i]);
else dp[i][j] = dp[i-1][j];
}
printf("%d\n", dp[M][T]);
}

return 0;
}

#include<stdio.h>
int dp[101][1001],time[101],p[101];
int max(int a,int b)
{
if(a>b)return a;
else return b;
}
int main()
{
int i,j,t,m;
scanf("%d%d",&t,&m);
for(i=0;i<m;i++)
{
scanf("%d%d",&time[i],&p[i]);
}
for(i=m-1;i>=0;i--)
{
for(j=0;j<=t;j++)
{
dp[i][j]=(i==m-1?0:dp[i+1][j]);
if(j>=time[i])dp[i][j]=max(dp[i][j],dp[i+1][j-time[i]]+p[i]);
}
}
printf("%d",dp[0][t]);
return 0;
}

uses math;
var t,m,i,j:longint;
a:array[0..100,1..2]of longint;
f:array[0..10000]of longint;
procedure init;
begin
read(t,m);
for i:=1 to m do readln(a[i,1],a[i,2]);
end;
procedure dp;
begin
for i:=1 to m do
for j:=t downto 0 do
if (j>=a[i,1]) then f[j]:=max(f[j-a[i,1]]+a[i,2],f[j]);
write(f[t]);
end;
begin
init;
dp;
end.

uses math;
var t,m,i,j:longint;
a:array[0..100,1..2]of longint;
f:array[0..10000]of longint;
procedure init;
begin
read(t,m);
for i:=1 to m do readln(a[i,1],a[i,2]);
end;
procedure dp;
begin
for i:=1 to m do
for j:=t downto 0 do
if (j>=a[i,1]) then f[j]:=max(f[j-a[i,1]]+a[i,2],f[j]);
write(f[t]);
end;
begin
init;
dp;
end.

别问我为什么交这么多次，我就是想知道怎么弄才能弄成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;
}