184 条题解

  • 0
    @ 2013-05-04 15:47:19

    捆绑法好理解适用范围也广。

    program P1313;
    var Left,Right,v,p:array[1..60] of longint;
    f:array[0..32000] of longint;
    Cu:array[1..60] of boolean;
    i,j,N,m,q:longint;

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

    begin
    fillchar(Left,sizeof(Left),0);
    fillchar(Right,sizeof(Right),0);

    readln(N,m);
    for i:=1 to m do begin
    readln(v[i],p[i],q);
    Cu[i]:=(q=0);
    if q<>0 then
    if Left[q]=0 then Left[q]:=i else Right[q]:=i;
    end;

    fillchar(f,sizeof(f),0);
    for i:=1 to m do
    if Cu[i] then
    for j:=N downto v[i] do begin
    f[j]:=max(f[j],f[j-v[i]]+v[i]*p[i]);
    if Left[i]<>0 then
    if j-v[i]-v[Left[i]]>=0 then f[j]:=max(f[j],f[j-v[i]-v[Left[i]]]+v[i]*p[i]+v[Left[i]]*p[Left[i]]);

    if Right[i]<>0 then
    if j-v[i]-v[Right[i]]>=0 then f[j]:=max(f[j],f[j-v[i]-v[Right[i]]]+v[i]*p[i]+v[Right[i]]*p[Right[i]]);

    if (Left[i]<>0) and (Right[i]<>0) then
    if j-v[i]-v[Left[i]]-v[Right[i]]>=0 then
    f[j]:=max(f[j],f[j-v[i]-v[Left[i]]-v[Right[i]]]+v[i]*p[i]+v[Left[i]]*p[Left[i]]+v[Right[i]]*p[Right[i]]);
    end;

    writeln(f[N]);
    end.

  • 0
    @ 2013-02-22 08:17:03

    分组,两个三次循环 OK

  • 0
    @ 2012-11-01 22:28:47

    这是一个典型的有依赖的背包,实际上也就是一个加了点小小限制的分组背包;

    首先,我们先对物品进行分组;用v[i]记录i的价钱(也就是重量),w[i]记录i的价值,c记录i的附件个数,c表示i的第j个附件的编号,c=-1代表这是附件;

    read(n,m);

    n:=n div 10;

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

    for i:=1 to m do

    begin

    read(v[i],w[i],q);

    w[i]:=v[i]*w[i];

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

    if q0 then

    begin

    inc(c[q,0]);

    c[q,c[q,0]]:=i;

    c:=-1;

    end;

    end;

    然后是动归模块:

    我们用num[k,j]表示总花费为j时,得到最大价值f[j]是否用到k组的主件;则枚举每一组的副件i时,就有

    f[j]:= max {f[j-v[k]-v[c[k,i]]]+w[k]+wc[k,i],

    f[j-v[c[k,i]]]+wc[k,i]}

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

    fillchar(num,sizeof(num),0);

    for k:=1 to m do

    if c[k,0]>=0 then

    begin

    for j:=n downto v[k] do

    begin

    if f[j]

  • 0
    @ 2010-07-09 23:24:11

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 25ms

    ├ 测试数据 09:答案正确... 103ms

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

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

    Accepted 有效得分:100 有效耗时:128ms

    见之有依赖的背包问题

    由于用了STL,速度太慢

  • 0
    @ 2010-04-13 00:10:28

    仍然是背包问题。。。

    #include

    #include

    int n,m;

    int cost[61],v[61],q[61],son[61][2],sonn[61];

    int f[32001];

    int max(int a,int b){return a>b?a:b;}

    int main()

    {

    memset(cost,0,sizeof(cost));

    memset(v,0,sizeof(v));

    memset(q,0,sizeof(q));

    memset(son,-1,sizeof(son));

    memset(sonn,0,sizeof(sonn));

    memset(f,0,sizeof(f));

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

    for(int i=1;i0 && j - cost[ son[i][0] ] >= 0 )

    tmp = max(tmp,f[j-cost[ son[i][0] ]] + v[ son[i][0] ]);

    if(sonn[i]>1 && j - cost[ son[i][1] ] >= 0 )

    tmp = max(tmp,f[j-cost[ son[i][1] ]] + v[ son[i][1] ]);

    if(sonn[i]>1 && j - cost[ son[i][0] ] - cost[ son[i][1] ] + cost[i] >= 0 )

    tmp = max(tmp,f[j-cost[ son[i][0] ]-cost[ son[i][1] ] + cost[i]] + v[ son[i][0] ] + v[ son[i][1] ] - v[i]);

    f[j] = tmp;

    }

    printf("%d\n",f[n]);

    }

  • 0
    @ 2010-04-05 20:24:01

    二维的交了几次都WA掉..直接改成一维的一次AC..郁闷..

  • 0
    @ 2009-11-10 11:01:47

    编译通过...

    ├ 测试数据 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,j,k,c,t,s:longint;

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

    a,b,num:array[0..60] of longint;

    v,w,d:array[0..60,0..4] of longint;

    begin

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

    fillchar(num,sizeof(num),0);

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

    for i:=0 to 60 do d:=-1;

    a[0]:=0;b[0]:=0;

    readln(n,m);

    for i:=1 to m do

    begin

    readln(a[i],b[i],c);

    b[i]:=a[i]*b[i];

    if c0 then

    begin

    inc(num[c]);

    d[c,num[c]]:=i;

    end

    else

    d:=0;

    end;

    t:=0;

    for i:=1 to m do

    if d=0 then

    begin

    inc(t);

    v[t][1]:=a[i];w[t][1]:=b[i];

    v[t][2]:=a[i]+a[d]; w[t][2]:=b[i]+b[d];

    v[t][3]:=a[i]+a[d]; w[t][3]:=b[i]+b[d];

    v[t][4]:=a[i]+a[d]+a[d]; w[t][4]:=b[i]+b[d]+b[d];

    end;

    for i:=1 to t do

    for j:=n downto 1 do

    begin

    for k:=1 to 4 do

    if (v

  • 0
    @ 2009-11-09 19:22:17

    不幸啊,等号输成了不等,没编译直接交,只过了两点。。。。。

    改后,AC了。。。。

    我的通过率。。。。

  • 0
    @ 2009-11-04 07:58:38

    主副捆绑,很容易解决

    var

    f:array[0..61,-20000..20000]of longint;

    n,m,k,i,j,v1,w1,q,z:longint;

    h:array[0..61]of longint;

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

    function max(a,b,c,d,e:longint):longint;

    begin

    if a>b then max:=a

    else max:=b;

    if c>max then max:=c;

    if d>max then max:=d;

    if e>max then max:=e;

    end;

    begin

    readln(n,m);

    k:=0;

    for i:=1 to m do

    begin

    readln(v1,w1,q);

    v1:=v1 div 10;

    if q=0 then begin inc(k);v[k,0]:=v1;w[k,0]:=w1;h[i]:=k end

    else

    begin

    z:=h[q];

    for j:=1 to 2 do

    if v[z,j]=0 then

    begin

    v[z,j]:=v1;

    w[z,j]:=w1;

    break;

    end;

    end;

    end;

    for i:=0 to 61 do

    for j:=-20000 to -1 do

    f:=-10000;

    f[0,0]:=0;

    n:=n div 10;

    for i:=1 to k do

    for j:=1 to n do

    f:=max(f,f[i-1,j-v]+v*w,

    f[i-1,j-v-v]+v*w+v*w,

    f[i-1,j-v-v]+v*w+v*w,

    f[i-1,j-v-v-v]+v*w+v*w+v*w);

    writeln(f[k,n]*10);

    end;

  • 0
    @ 2009-11-03 22:17:25

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-11-03 08:28:52

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 9ms

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

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

    Accepted 有效得分:100 有效耗时:9ms

    昨天脑子小了,囧,今天1下就A了

  • 0
    @ 2009-11-02 22:00:47

    这弱智题目都交了两遍

    我以后没脸活着见人了,还是去跳楼吧。。。

    但是想了好久,想到vijos上还有好多水题给我刷,所以还是放弃死的念头了。

    如果有吃错了毒药的,可以看看我的丑程序来洗胃——保证你把吃的什么都吐光。

    program p1313;

    var

    m,n,i,j,k,l,a,b,cc,p:longint;

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

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

    t,r:array[1..60] of longint;

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

    begin

    if a>b then exit(a);

    exit(b);

    end;

    begin

    readln(n,m);

    for i:=1 to m do

    begin

    readln(a,b,cc);

    if cc=0 then

    begin

    inc(p);

    r[i]:=p;

    w[p,0]:=a;

    c[p,0]:=a*b;

    end else

    begin

    inc(t[r[cc]]);

    if t[r[cc]]=1 then

    begin

    w[r[cc],1]:=w[r[cc],0]+a;

    c[r[cc],1]:=c[r[cc],0]+a*b;

    end;

    if t[r[cc]]=2 then

    begin

    w[r[cc],2]:=w[r[cc],0]+a;

    c[r[cc],2]:=c[r[cc],0]+a*b;

    w[r[cc],3]:=w[r[cc],1]+a;

    c[r[cc],3]:=c[r[cc],1]+a*b;

    end;

    end;

    end;

    for i:=1 to p do

    for j:=n downto w do

    begin

    f[j]:=max(f[j],f[j-w]+c);

    if (w0) and (j>=w) then

    f[j]:=max(f[j],f[j-w]+c);

    if w0 then

    begin

    if (j>=w) then

    f[j]:=max(f[j],f[j-w]+c);

    if (j>=w)then

    f[j]:=max(f[j],f[j-w]+c);

    end;

    end;

    writeln(f[n]);

    end.

  • 0
    @ 2009-11-01 09:06:22

    for j:=1 to m do

    for i:=1 to t do

    begin

    if j>=p

    then f:=max(f,f[i-1,j-p]+v) else f:=f;{else f:=f;这句相当重要。}

    if (p0)and(j>=p+p)

    then f:=max(f,f[i-1,j-p-p]+v+v);

    if (p0)and(j>=p+p)

    then f:=max(f,f[i-1,j-p-p]+v+v);

    if (p0)and(j>=p+p+p)

    then f:=max(f,f[i-1,j-p-p-p]+v+v+v);

    end;

  • 0
    @ 2009-10-31 13:46:23

    那个...啥..

    弱弱的问下.

    为啥我直接dp判断附件的主件是否已经买下来

    这样就不能ac捏.

    急需大牛求解

    附程序:

    var

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

    f:array[0..100]of boolean;

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

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

    procedure work(q,w:longint);

    begin

    if ql then

    begin

    if (w+b[q+1,1]

  • 0
    @ 2009-10-30 23:19:12

    我沙茶了、DP判断分析的还不够仔细、、

    今天的模拟题也就因为漏了一个判断全WA了、

    教训啊、、

  • 0
    @ 2009-10-29 20:39:04

    type arr=record

    l:longint;

    r:longint;

    end;

    var c:array[0..60] of arr;a:array[0..60,0..60] of longint;q,v,n,xx,yy,zz,ii:longint;

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

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

    procedure search(x,y:longint);

    var max,k:longint;

    begin

    if y-1 then

    if f[c[x].l,k]=-1 then

    search(c[x].l,k);

    if c[x].r>-1 then

    if f[c[x].r,y-p[x]-k]=-1 then

    search(c[x].r,y-p[x]-k);

    if f[c[x].l,k]+f[c[x].r,y-p[x]-k]>max then

    max:=f[c[x].l,k]+f[c[x].r,y-p[x]-k];

    end;

    max:=max+w[x]*p[x];

    if c[x].r-1 then

    if f[c[x].r,y]=-1 then

    search(c[x].r,y);

    if f[c[x].r,y]>max then

    max:=f[c[x].r,y];

    f[x,y]:=max;

    end;

    procedure play(x:longint);

    var r:longint;

    begin

    if a[x,0]=0 then exit;

    c[x].l:=a[x,1];

    for r:=2 to a[x,0] do

    c[a[x,r-1]].r:=a[x,r];

    end;

    begin

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

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

    read(v,n);

    for ii:=1 to n do

    begin

    read(xx,yy,zz);

    a[zz,0]:=a[zz,0]+1;

    a[zz,a[zz,0]]:=ii;

    p[ii]:=xx;

    w[ii]:=yy;

    end;

    for ii:=0 to 60 do

    for q:=0 to 32000 do

    f[ii,q]:=-1;

    for ii:=0 to 60 do

    begin

    c[ii].l:=-1;

    c[ii].r:=-1;

    end;

    for ii:=0 to n do

    play(ii);

    search(a[0,1],v);

    write(f[a[0,1],v]);

    close(input);

    close(output);

    end.

    我强大的使用的树型DP 过一半!!和裸搜一样一样的

  • 0
    @ 2009-10-29 17:45:36

    呃,C的程序实在太少了。。。

    发个补充下吧。。

    就是个依赖型的背包~~

    #include

    struct

    {

    int cost;

    int right;

    }save[61][5],step[61][5];

    int form[32001];

    int n,m;

    int main()

    {

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

    int i,j,k,cost,right,tag,top=0;

    n/=10;

    for(i=1;i=1;j--)

    if(tag==save[j][0].right)

    {

    save[j][0].cost++;

    save[j][save[j][0].cost].cost=cost/10;

    save[j][save[j][0].cost].right=right;

    break;

    }

    }

    }

    for(i=1;i1)

    {

    step[i][0].cost=2;

    step[i][2].cost=save[i][1].cost+save[i][2].cost;

    step[i][2].right=step[i][1].right+save[i][2].cost*save[i][2].right*10;

    }

    if(save[i][0].cost>2)

    {

    step[i][0].cost=4;

    step[i][3].cost=save[i][1].cost+save[i][3].cost;

    step[i][3].right=step[i][1].right+save[i][3].cost*save[i][3].right*10;

    step[i][4].cost=step[i][2].cost+save[i][3].cost;

    step[i][4].right=step[i][2].right+save[i][3].cost*save[i][3].right*10;

    }

    }

    for(i=1;i=step[i][1].cost;j--)

    {

    for(k=1;k=step[i][k].cost) form[j]=(form[j]>form[j-step[i][k].cost]+step[i][k].right)?form[j]:form[j-step[i][k].cost]+step[i][k].right;

    }

    }

    printf("%d\n",form[n]);

    return 0;

    }

  • 0
    @ 2009-10-29 15:10:49

    瞧这猥琐的01背包。。

  • 0
    @ 2009-10-27 13:01:10

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

    write(max1);

    end.

  • 0
    @ 2009-10-26 20:59:30

    10min不到,秒杀.

    终于100A了......没想到我的第100A竟然是这题......

信息

ID
1313
难度
6
分类
动态规划 | 背包 点击显示
标签
递交数
8322
已通过
2462
通过率
30%
被复制
19
上传者