好水的背包

⊙﹏⊙b汗（竟然交了三次）

program dfs;

const

maxn=30000;

maxm=25;

var

n,m,i,j:integer;

v,p:array[1..maxm] of integer;

f:array[0..maxn+1] of longint;

begin

readln(n,m);

for i:=1 to m do

readln(v[i],p[i]);

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

for i:=1 to m do

for j:=n downto v[i] do

if f[j-v[i]]+v[i]*p[i]>f[j]

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

writeln(f[n]);

end.

强烈抗议出题人忽悠做题者！！！！！

提醒WA的小心：所有的数据范围都给小了，数据中比题目中的要大得多，所以，数组尽量开大，所有的变量都要改成longint，这样才可以0msAC

状态转移方程：

f=max( a[j-v[i]],a[j] )

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

数组要大大的开啊 ，越大越好！怪哉！

一个程序 提交两次

第一次：

编译失败...|错误号:-1

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

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

第二次：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

详见：

http://www.vijos.cn/Record_Show.asp?id=1161947

http://www.vijos.cn/Record_Show.asp?id=1161948

为什么 Vivid Puppy 也会出现这样的问题？

Vijos 的内存限制到底是多少？

交了N次,数组开小了,以后有多大开多大的数组!!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

背包的变形

每个物品的价值=钱 * 重要度

范围啊害我wa了n次

最后修改：

var f:array[0..30,0..100000]of longint;

val,w,z:array[1..30] of longint;

i,j,k,l,t,m,n:longint;

。。。。。。

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1317;

const

maxn=30000;

maxm=25;

var

n,m,i,j:integer;

v,p:array[1..maxm] of integer;

f:array[0..maxn+1] of longint;

begin

readln(n,m);

for i:=1 to m do

readln(v[i],p[i]);

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

for i:=1 to m do

for j:=n downto v[i] do

if f[j-v[i]]+v[i]*p[i]>f[j]

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

writeln(f[n]);

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 p1317;

const

maxn=30000;

maxm=25;

var

n,m,i,j:integer;

v,p:array[1..maxm] of integer;

f:array[0..maxn+1] of longint;

begin

readln(n,m);

for i:=1 to m do

readln(v[i],p[i]);

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

for i:=1 to m do

for j:=n downto v[i] do

if f[j-v[i]]+v[i]*p[i]>f[j]

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

writeln(f[n]);

end.

一次AC...

Flag 　　Accepted

题号 　　P1317

类型(?) 　　动态规划

通过 　　3000人

提交 　　6323次

通过率 　　47%

难度 　　2

第3000个！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

maxw,n,i,j,x:integer;

w,v:array[0..25]of longint;

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

begin

readln(maxw,n);

for i:=1 to n do begin read(w[i],x); v[i]:=w[i]*x; end;

for i:=1 to n do

for j:=maxw downto w[i] do

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

writeln(f[maxw]);

end.

Flag 　　 Accepted

题号 　　P1317

类型(?) 　　动态规划

通过 　　2983人

提交 　　6296次

通过率 　　47%

难度 　　2

提交 讨论 题解

program happy(input,output);

var

m1:longint;

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

w,c:array[1..25] of integer;

f:array[0..25,0..30000] of longint;

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

begin

if x>y then max:=x else max:=y;

end;

begin

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

readln(m,n);

for i:= 1 to n do

begin

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

end;

for i:= 1 to n do

for j:= 1 to m do

begin

if j

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

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

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

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

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

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

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

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

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

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

秒杀！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次同滚动啊!还有点小激动呢!

附My solution:

program p1317;

var n,m,i,j:longint;

v,p:array[1..25] of longint;

data:array[1..30000] of longint;

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

begin

if a>b then exit(a)

else exit(b);

end;

begin

readln(n,m);

for i:=1 to m do

readln(v[i],p[i]);

for i:=1 to m do

for j:=n downto v[i] do

data[j]:=max(data[j],data[j-v[i]]+v[i]*p[i]);

writeln(data[n]);

end.

与01背包一样，钱相当于背包空间，钱乘重要度相当于价值，背代码就可以了。

这是我在学校编的，可惜上不去网，回来测一下。

program happy;

var i,j,k,n,m:integer;

rec:array[0..30001]of longint;

a,b:longint;

begin

assign(input,'happy.in');assign(output,'happy.out');reset(input);rewrite(output);

read(n,m);fillchar(rec,sizeof(rec),0);

for i:=1 to m do

begin

read(a,b);b:=b*a;

for j:=n-a downto 0 do

if rec[j]+b>rec[j+a] then rec[j+a]:=rec[j]+b;

end;

write(rec[n]);

close(input);close(output);

end.