一直以为是DP有误，没想到是INIT的时候出了问题。如果要捆绑的话，那物品的总数就是主件的总数。但如果把附件存在主件的数组中，那么这个附件它的主件编号就不是C了，C是主件在所有物品中的编号，而不是主件在我们的数组中的编号。有人懂了吗？好，手可以放下了，我知道你不懂，那我就不说了。

program v1;

var n,m,i,j,k,max1:longint;

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

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

c,d:array[1..60,0..3]of longint;

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

begin

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

end;

begin

readln(m,n);

for i:=1 to n do readln(v[i],p[i],q[i]);

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

for i:=1 to n do

if q[i]=0 then begin c:=v[i]*p[i];d:=v[i];end

else begin

if c[q[i],1]=0 then begin c[q[i],1]:=c[q[i],0]+v[i]*p[i];d[q[i],1]:=d[q[i],0]+v[i];end

else begin c[q[i],2]:=c[q[i],0]+v[i]*p[i];d[q[i],2]:=d[q[i],0]+v[i];

c[q[i],3]:=c[q[i],1]+v[i]*p[i];d[q[i],3]:=d[q[i],1]+v[i];end;

end;

for k:=1 to n do

if q[k]=0 then

for j:=m downto 0 do

for i:=0 to 3 do

if (j>=d[k,i])and(c[k,i]0) then f[j]:=max(f[j],f[j-d[k,i]]+c[k,i]);

max1:=0;

for i:=1 to m do if f[i]>max1 then max1:=f[i];writeln(max1);

readln;

readln

end.

var

max1,n,m,i,j,x:longint;

f:array[1..60] of boolean;

v,p:array[0..60] of longint;

b:array[1..60,0..2] of longint;

a:array[0..32000] of longint;

function max(j,k:longint):longint;

begin

if j>k then exit(j)

else exit(k);

end;

begin

readln(n,m);

fillchar(f,sizeof(f),true);

for i:=1 to m do

begin

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

read(x);

if x0 then begin b[x,0]:=b[x,0]+1;b[x,b[x,0]]:=i;f[i]:=false; end;

readln;

end;

fillchar(a,sizeof(a),0);

for i:=1 to m do

if f[i] then

begin

for j:=n downto v[i] do

begin

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

if (b>=1) and (j-v[i]-v[b]>=0) then a[j]:=max(a[j-v[i]-v[b]]+v[i]*p[i]+v[b]*p[b],a[j]);

if (b=2) and (j-v[i]-v[b]>=0) then a[j]:=max(a[j-v[i]-v[b]]+v[i]*p[i]+v[b]*p[b],a[j]);

if (b=2) and (j-v[i]-v[b]-v[b]>=0) then a[j]:=max(a[j-v[i]-v[b]-v[b]]+v[i]*p[i]+v[b]*p[b]+v[b]*p[b],a[j]);

end;

end;

max1:=0;

for i:=0 to n do

if a[i]>max1 then max1:=a[i];

writeln(max1);

end.

一次ACACAC 秒杀

.0......................................

program p1313;

type rec=record

w,p,k,g:longint;

end;

var n,m:Longint;

a:array[1..200,0..3]of rec;

f:array[0..60,0..32000]of longint;

procedure init;

var i,x,y,z:longint;

begin

readln(n,m);

for i:=1 to m do

begin

readln(x,y,z);

a.w:=x;

a.p:=x*y;

a.k:=z;

end;

end;{input}

procedure head;

var j,i:longint;

begin

for i:=1 to m do

if a.k0 then

begin

j:=a.k;

inc(a[j,0].g);

a[j,a[j,0].g].w:=a.w+a[j,0].w;

a[j,a[j,0].g].p:= a.p+a[j,0].p;

if a[j,0].g=2 then

begin

j:=a.k;

inc(a[j,0].g);

a[j,3].w:=a[j,1].w+a.w;

a[j,3].p:=a[j,1].p+a.p;

end; a.w:=maxlongint;

end;

end;

procedure dp;

var i,j,k:longint;

begin

for i:=1 to m do

for j:=1 to n do

begin

f:=f;

for k:=0 to a.g do

if j>=a.w then

if f

分组DP

建议去看看背包问题九讲 蛮有帮助的

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

对于我们这种初学者来说实数难题，不过在各位大牛的题解帮助下终于编出来了，秒杀……

Var n,m,i:longint; data{状态转移方程的值}:array[0..100,0..32000]of longint;

v{价格},p{重要度->乘积}:array[0..100,0..10]of longint; s{主件的附件数},c{附件的主件编号}:array[0..100]of integer;

Procedure try(i,j:longint);{求解过程，i为剩余物品数目，j为剩余钱数}

var x,y,k:longint;

begin

x:=0; y:=0;

if (i=0)or(j=v then

begin

if data[i-1,j-v]=0 then try(i-1,j-v);

if data[i-1,j-v]+p>x then x:=data[i-1,j-v]+p;

end;

if x>=y then data:=x else begin data:=y; end;

end;

Begin

readln(n,m);

for i:=1 to m do

begin

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

p:=v*p;{为了程序简便和高效，P数组代替后面的乘积}

if c[i]0 then{捆绑过程}

begin

inc(s[c[i]]); {主件+附件}

v[c[i],s[c[i]]]:=v+v[c[i],0];

p[c[i],s[c[i]]]:=p+p[c[i],0];

if s[c[i]]=2 then

begin

inc(s[c[i]]); {主件+附件1+附件2}

v[c[i],3]:=v[c[i],1]+v;

p[c[i],3]:=p[c[i],1]+p;

end;

v:=9999999;{记住捆绑后删除原附件}

end;

end;

fillchar(data,sizeof(data),0);{赋初值，个人认为没用，但习惯了赋-1，这道题赋-1和导致结果比答案少1，无法理解}

try(m,n);

writeln(data[m,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 p4;

var

q,p,fu:array[1..100] of integer;

w,c:array[1..100,0..3] of longint;

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

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

max:longint;

begin

assign(input,'budget.in'); reset(input);

assign(output,'budget.out'); rewrite(output);

read(n,m);

fillchar(fu,sizeof(fu),0);

for i:=1 to m do begin read(w,p[i],q[i]); c:=w*p[i]; end;

for i:=1 to m do

begin

if q[i]>0 then begin inc(fu[q[i]]);

w[q[i],fu[q[i]]]:=w[q[i],0]+w; c[q[i],fu[q[i]]]:=c[q[i],0]+c; end;

if fu[q[i]]=2 then

begin

inc(fu[q[i]]);

w[q[i],fu[q[i]]]:=w[q[i],1]+w; c[q[i],fu[q[i]]]:=c[q[i],1]+c;

end;

end;

f[0]:=0;

for i:=1 to m do

if q[i]=0 then

for j:=n downto w do

begin

max:=f[j];

for k:=0 to fu[i] do

if (j>=w) and (f[j-w]+c>max) then max:=f[j-w]+c;

f[j]:=max;

end;

write(f[n]);

close(input); close(output);

end.

经典的01背包做一点变化即可

这是传说中的有依赖的背包问题吧，好像一个字都不用动

想用通解TreeDP去AC结果TLE……只有30分……

只好换成朴素的01bag，居然AC……

无语……

PS：我借鉴了一下小岛神牛的简化代码方法……

{——————————我是分割线——————————}

编译通过...

├ 测试数据 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

var a,b:array[0..100,0..3]of longint;

v,q,p,me:array[0..61]of longint;

f:array[0..100,0..3201]of longint;

n,max1,m,xx,xy:longint;

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

begin

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

end;

procedure init;

var i:longint;

begin

readln(n,m);

fillchar(a,sizeof(a),0);

fillchar(b,sizeof(b),0);

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

n:=n div 10;

for i:=1 to m do

begin

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

v[i]:=v[i] div 10;

end;

end;

procedure doit;

var i,j,k:longint;

begin

max1:=0;

for i:=1 to m do

begin

if q[i]>0 then

begin

if a[q[i],1]=0 then

begin

a[q[i],1]:=v[i];

b[q[i],1]:=p[i];

end

else

begin

a[q[i],2]:=v[i];

b[q[i],2]:=p[i];

end;

end

else

begin

a:=v[i];

b:=p[i];

end;

end;

for i:=1 to m do

for j:=0 to n do

begin

f:=f;

if q[i]=0 then

begin

fillchar(me,sizeof(me),0);

if j>=v[i] then

me[1]:=f+v[i]*p[i];

if (j>=a+v[i])and(a>0){and(i>=2)} then

me[2]:=f[i-1,j-a-v[i]]+a*b+v[i]*p[i];

if (j>=a+v[i])and(a>0){and(i>=2)} then

me[3]:=f[i-1,j-a-v[i]]+a*b+v[i]*p[i];

if (j>=a+v[i]+a)and(a>0)and{(i>=3)and}(a>0) then

me[4]:=f[i-1,j-a-v[i]-a]+a*b+v[i]*p[i]+a*b;

for k:=1 to 4 do f:=max(f,me[k]);

{if f>max1 then

begin

max1:=f;

// xx:=i;

// xy:=j;

end;}

end;

end;

end;

procedure outtit;

var i,j:longint;

begin

{ for i:=1 to m do

begin

for j:=0 to n do write(f,' ');

writeln;

end; }

for i:=1 to m do if f>max1 then max1:=f;

write(max1,0);

//writeln(xx,' ',xy);

end;

begin

init;

doit;

outtit;

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个或2个附件。'

~!@$$%^ ... 看了题目N遍才看到..orz..

so easy !

动归方程：

fun(m,i-1);

f[m][i]=max(f[m][i],f[m]);

if (m-a[i].mon>=0)

{

fun(m-a[i].mon,i-1);

f[m][i]=max(f[m][i],f[m-a[i].mon]+a[i].p*a[i].mon);

}

if (m-a[i].mon-a[i].m1>=0)

{

fun(m-a[i].mon-a[i].m1,i-1);

f[m][i]=max(f[m][i],f[m-a[i].mon-a[i].m1]+a[i].p*a[i].mon+a[i].m1*a[i].p1);

}

if (m-a[i].mon-a[i].m2>=0)

{

fun(m-a[i].mon-a[i].m2,i-1);

f[m][i]=max(f[m][i],f[m-a[i].mon-a[i].m2]+a[i].p*a[i].mon+a[i].m2*a[i].p2);

}

if (m-a[i].mon-a[i].m1-a[i].m2>=0)

{

fun(m-a[i].mon-a[i].m1-a[i].m2,i-1);

f[m][i]=max(f[m][i],f[m-a[i].mon-a[i].m1-a[i].m2]+a[i].p*a[i].mon+a[i].p1*a[i].m1+a[i].p2*a[i].m2);

}

只需对主件和附件处理下就行了，可以用结构体

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最后分f:array[1..100,1..32000] 才过的

大牛解释下为什么我原来的是错的

var n,m:longint;

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

v,s:array[1..60] of longint;

_v,p,q,i,j,sum,k:longint;

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

begin

if a>b then exit(a) else exit(b);

end;

begin

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

readln(n,m);

for i:=1 to m do

begin

readln(_v,p,q);

if q=0 then

begin

inc(sum);

v[sum]:=_v;

s[sum]:=_v*p;

end;

if q>0 then

begin

v[q]:=v[q]+_v;

s[q]:=s[q]+_v*p;

end;

end;

for i:=1 to sum do

for j:=32000 downto v[i] do

f[j]:=max(f[j],f[j-v[i]]+s[i]);

writeln(f[n]);

end.

var a:array[1..60] of record

v,m,v1,m1,v2,m2:longint;

s:boolean;

end;

i,j,m,n,x,y,z,t1,t2:longint;

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

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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

begin

if a>b then exit(a) else exit(b);

end;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

begin

readln(n,m);

n:=n div 10;

for i:=1 to m do

begin

readln(x,y,z);

if z=0 then begin

a[i].s:=true;

a[i].v:=x div 10;

a[i].m:=y*a[i].v;

end;

if z0 then

begin

if a[z].v1=0 then

begin

a[z].v1:=x div 10;

a[z].m1:=y*a[z].v1;

end

else

begin

a[z].v2:=x div 10;

a[z].m2:=y*a[z].v2;

end;

end;

end;

for i:=1 to m do

if a[i].s then

for j:=n downto a[i].v do

begin

if (j-a[i].v>=0) then

f[j]:=max(f[j],f[j-a[i].v]+a[i].m);

if (a[i].v10)and(a[i].m10) then

if (j-a[i].v-a[i].v1>=0) then

f[j]:=max(f[j],f[j-a[i].v-a[i].v1]+a[i].m+a[i].m1);

if (a[i].v20)and(a[i].m20) then

begin

if (j-a[i].v-a[i].v2>=0) then

f[j]:=max(f[j],f[j-a[i].v-a[i].v2]+a[i].m+a[i].m2);

if (j-a[i].v-a[i].v1-a[i].v2>=0) then

f[j]:=max(f[j],f[j-a[i].v-a[i].v1-a[i].v2]+a[i].m+a[i].m1+a[i].m2);

end;

end;

writeln(f[n],'0');

end.

！！： 第 j 行 输入的是编号为 j-1 的数据，读入附件的时候主件编号也是在加的。 这时该编号就没有主件 ！！！！！

想吐血....编好才发现求的是....的积

我求了价值最大...

可恶，太玩人了。

明明60件物品，结果只过8个数据；数组改成80，过9个；改成100才AC。

program qwe;

var f:array[0..100,0..32000]of longint;

g:array[1..100,1..2]of integer;

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

t:array[1..100]of 0..2;

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

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

begin

if a>b then max:=a

else max:=b;

end;

begin

read(n,m);

for i:=1 to m do

begin

read(c[i],v[i],p[i]);

if p[i]0 then

begin

inc(t[p[i]]);

g[p[i],t[p[i]]]:=i;

end;

end;

for k:=1 to m do

if p[k]=0 then

begin

inc(i);

for j:=1 to n do

case t[k] of

0:begin

f:=f;

if j>=c[k] then f:=max(f,f[i-1,j-c[k]]+c[k]*v[k]);

end;

1:begin

f:=f;

if j>=c[k] then f:=max(f,f[i-1,j-c[k]]+c[k]*v[k]);

if j>=c[k]+c[g[k,1]] then

f:=max(f,

f[i-1,j-c[k]-c[g[k,1]]]+c[k]*v[k]+c[g[k,1]]*v[g[k,1]]);

end;

2:begin

f:=f;

if j>=c[k] then f:=max(f,f[i-1,j-c[k]]+c[k]*v[k]);

if j>=c[k]+c[g[k,1]] then

f:=max(f,f[i-1,

j-c[k]-c[g[k,1]]]+c[k]*v[k]+c[g[k,1]]*v[g[k,1]]);

if j>=c[k]+c[g[k,2]] then

f:=max(f,f[i-1,

j-c[k]-c[g[k,2]]]+c[k]*v[k]+c[g[k,2]]*v[g[k,2]]);

if j>=c[k]+c[g[k,1]]+c[g[k,2]] then

f:=max(f,f[i-1,j-c[k]-c[g[k,1]]-c[g[k,2]]]

+c[k]*v[k]+c[g[k,1]]*v[g[k,1]]+c[g[k,2]]*v[g[k,2]])

end;

end;

end;

writeln(f);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

猥琐猥琐猥琐

脑袋有点晕 做了三次都不对

一气之下 第四次刚做完 直接提交 AC了 rp。。。。。。。。。

program asd;

var

f:array[1..80,0..3200]of integer;

ch:array[1..60]of boolean;

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

child:array[1..60]of array[0..3]of integer;

max:longint;

ma,q,n,i,j,m,k:integer;

begin

readln(n,m);

n:=n div 10;

fillchar(ch,sizeof(ch),true);

for i:=1 to m do

begin

readln(v[i],p[i],q);v[i]:=v[i]div 10;

if q=0 then w[i]:=v[i]*p[i] else

begin inc(child[q][0]);child[q][child[q][0]]:=i; end;

end;k:=m;

for i:=1 to m do

if child[i][0]>0 then

begin

inc(k);v[k]:=v[i]+v[child[i][1]];w[k]:=w[i]+v[child[i][1]]*p[child[i][1]];

child[i][3]:=k;

if child[i][0]>1 then

begin

inc(k);v[k]:=v[i]+v[child[i][2]];w[k]:=w[i]+v[child[i][2]]*p[child[i][2]];

inc(k);v[k]:=v[i]+v[child[i][1]]+v[child[i][2]];

w[k]:=w[i]+v[child[i][1]]*p[child[i][1]]+v[child[i][2]]*p[child[i][2]];

end;

end;

for j:=v[1] to n do

begin

max:=w[1];

if child[1][0]>0 then

begin

if (j>=v[child[1][3]])and(max1 then

begin

if(j>=v[child[1][3]+1])and(max=v[child[1][3]+2])and(max=v[i])and(f+w[i]>ma) then ma:=f+w[i];

if child[i][0]>0 then

begin

if(j>=v[child[i][3]])and(ma1 then

begin

if(j>=v[child[i][3]+1])and(ma=v[child[i][3]+2])and(mamax then max:=ma;

f:=ma;

end;

max:=max*10;

writeln(max);

end.

var i,j,m,n,z,num:longint;

code,count:array[0..70] of longint;

p,w:array[0..70,0..5] of longint;

f:array[0..70,0..3200] of longint;

begin

readln(n,m); n:=n div 10;

for i:=1 to m do

begin

readln(p,w,code[i]);

p:=p div 10;

z:=code[i];

w:=p*w;

if z>0 then

begin

inc(count[z]);

p[z,count[z]]:=p[z,0]+p;

w[z,count[z]]:=w[z,0]+w;

if count[z]=2 then

begin

inc(count[z]);

p[z,count[z]]:=p[z,1]+p;

w[z,count[z]]:=w[z,1]+w;

end;

end;

end;

num:=0;

for i:=1 to m do

if code[i]=0 then

begin

inc(num);

for z:=0 to count[i] do

for j:=1 to n do

begin

if f[num,j]=p then

if f[num,j]

怎么全是pascal的，咱来个正宗c++的

#include

using namespace std;

ifstream inf("budget.in");

ofstream ouf("budget.out");

int main()

{

int N,m,v[60],p[60],q[60],f[61][3200],a[61][4],b[61],c[61],d[61][4],t=0;

inf>>N>>m;

N=N/10;

for(int i=1;i>v[i]>>p[i]>>q[i];

v[i]=v[i]/10;

}

for(int i=1;i