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

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

0ms秒过

var
i,j,n,t:longint;
a,tt:array[1..100]of longint;
f:array[0..1000]of longint;
begin
read(n,t);
for i:=1 to n do read(a[i],tt[i]);
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=t downto tt[i] do
if j>=tt[i] then
if f[j-tt[i]]+a[i]>f[j] then
f[j]:=f[j-tt[i]]+a[i];
writeln(f[t]);
end.

#include <iostream>

using namespace std;

const int MAX_SIZE = 1000;

// 每个项目喜爱程度 每个项目花费时间 总的喜爱程度
int f[MAX_SIZE] = {0}, t[MAX_SIZE] = {0}, interest[MAX_SIZE] = {0};

int main()
{
//
// 输入数据
//
int N, timeTotal;
cin >> N;
cin >> timeTotal;

//
// 读入每个项目的喜爱程度和花费时间
//
int i, j;
for (i = 1; i <= N; i++) {
cin >> f[i] >> t[i];
}

//
// 背包DP
//
for (i = 1; i <= N; i++) {
for (j = timeTotal; j >= t[i]; j--) {
if (interest[j - t[i]] + f[i] > interest[j]) {
interest[j] = interest[j - t[i]] + f[i];
}
}
}

//
// 输出结果
//
cout << interest[timeTotal];

return 0;
}

纯粹是背包 不解释
不会压维的看一下啊
var i,j,k,l,n,m,ans:longint;
a,b,f:array[0..10000] of longint;

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

begin
readln(n);
readln(m);
for i:=1 to n do read(a[i],b[i]);
for i:=1 to n do
for j:=m downto 0 do if j-b[i]>=0 then f[j]:=max(f[j-b[i]]+a[i],f[j]);
for i:=0 to m do if f[i]>ans then ans:=f[i];
writeln(ans);
end.

var
g,c,r:array[0..1001] of longint;
n,t,i,j:longint;

begin
readln(n); readln(t);
for i:=1 to n do readln(g[i],c[i]);
for i:=1 to n do
for j:=t downto c[i] do
if r[j]<r[j-c[i]]+g[i] then
r[j]:=r[j-c[i]]+g[i];
j:=0;
for i:=1 to t do
if r[i]>j then
j:=r[i];
writeln(j);
end.

var
v,n,ans,i,j:longint;
w:array[0..100]of longint;
vv:array[0..100]of longint;
f:array[0..1201]of longint;

function max(aa,bb:longint):longint;
begin
if aa>bb then exit(aa) else exit(bb);
end;

procedure init;
begin
readln(n);
readln(v);
for i:=1 to n do
readln(w[i],vv[i]);
fillchar(f,sizeof(f),0);
end;

procedure dp;
begin
for i:=1 to n do
for j:=v downto vv[i] do
f[j]:=max(f[j-vv[i]]+w[i],f[j]);
end;

begin
init;
dp;
writeln(f[v]);
end.

数组一定要开大！！！！不然就爆了

program hero;
var value:array[0..1200] of longint;
t,i,j,m,a,b,max:longint;
begin
readln(m);readln(t);
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]+a>value[j+b] then value[j+b]:=value[j]+a;
end;
max:=-1;
for i:=t downto 0 do
if value[i]>max then max:=value[i];
writeln(max);
end.
好简短的程序。。。貌似是0s

和采药一样，，，

把之前写的程序读入一改都没编译就AC了= =
哦呵呵呵

点击查看程序源码+详细题解

点击这里查看

最基本的01背包。。一边读入一边背包就可以了。。用一维数组做。。详细做法参看dd神牛的背包九讲。。

小牛注意啦！

小牛注意啦！

如果开二维的数组进行递归，一定要写t downto 1 do！

var

n,s,i,j:integer;

f,t:array[1..100]of integer;

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

function da(x,y:longint):longint;

begin

da:=x; if x

这么多废话 其实就是简单的01背包

var

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

n,v,c,w,i,j:longint;

begin

readln(n,v);

for i:=1 to n do

begin

readln(w,c);

for j:=v downto c do

if f[j-c]+w>f[j] then f[j]:=f[j-c]+w

end;

writeln(f[v])

end.

都快忘了01背包怎么搞了……

program P1025;

var

i,j,n,t:longint;

a,tt:array[1..100]of longint;

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

begin

read(n,t);

for i:=1 to n do read(a[i],tt[i]);

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

for i:=1 to n do

for j:=t downto tt[i] do

if j>=tt[i] then

if f[j-tt[i]]+a[i]>f[j] then

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

writeln(f[t]);

end.

巨水的背包啊