168 条题解

  • 0
    @ 2009-08-10 16:28:16

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    二维背包

    F 表示质量I, 体积J 时最大卡路里, 然后就是个背包

    注意把数组开打一点, 我小家子气开400,结果WA了一会, 囧啊!

  • 0
    @ 2009-08-07 21:12:14

    二维背包

  • 0
    @ 2009-08-06 15:20:21

    #include

    #define M 400

    typedef struct {

    int v;

    int m;

    int e;

    }food;

    int f[M+1][M+1];

    int max(int a,int b)

    {

    return (a>b)?a:b;

    }

    int main()

    {

    int maxv,maxm,n;

    int i,j,k;

    food t[51];

    scanf("%d %d %d",&maxv,&maxm,&n);

    for (i = 1;i = 0;k--) {

    if ( j - t[i].v >= 0 &&k - t[i].m >= 0) {

    f[j][k] = max(f[j-t[i].v][k-t[i].m]+t[i].e,f[j][k]);

    }

    }

    }

    }

    printf("%d",f[maxv][maxm]);

    return 0;

    }

    有了方程做这个不费吹灰之力了,哈哈

  • 0
    @ 2009-08-05 10:43:49

    今天欣喜若狂啊 - -

    终于自己写出一道动态规划的题了``

    Var vm,mm:longint;

    f:array[1..400,1..400] of longint;

    i,n,v,m,k,a,b:longint;

    Begin readln(vm,mm);

    readln(n);

    for i:=1 to n do

    Begin

    readln(v,m,k);

    for a:=vm downto v do

    for b:=mm downto m do

    if f[a,b]

  • 0
    @ 2009-08-02 10:24:54

    编译通过...

    ├ 测试数据 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-07-27 11:38:11

    背包问题,博大精深。。。。。。

  • 0
    @ 2009-07-22 15:50:10

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

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

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

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

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

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

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

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

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

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

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

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

    #include

    void main()

    {

    int i,j,k,v,w,n,food[52][3]={0},record[502][502]={0};

    scanf("%d%d",&v,&w);

    scanf("%d",&n);

    for(i=1;i=food[i][1];k--)

    {

    if(record[j-food[i][0]][k-food[i][1]]+food[i][2]>record[j][k])

    {

    record[j][k]=record[j-food[i][0]][k-food[i][1]]+food[i][2];

    }

    }

    }

    }

    printf("%d\n",record[v][w]);

    }

    哈哈,这个题很简单嘛,二维背问题今天刚好研究完就刚好碰上了这个题,所以非常轻松!!!!

  • 0
    @ 2009-07-21 17:17:18

    program p1334;

    var v,m,w:array[1..50] of longint;

    i,j,k,l,n,o,p,q,maxv,maxm:longint;

    f:array[0..400,0..400] of longint;

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

    begin if x>y then exit(x);exit(y);end;

    begin

    readln(maxv,maxm);

    readln(n);

    for i:=1 to n do

    readln(v[i],m[i],w[i]);

    for i:=1 to n do

    for j:=maxv downto v[i] do

    for k:=maxm downto m[i] do

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

    writeln(f[maxv,maxm]);

    end.

  • 0
    @ 2009-07-13 15:23:17

    又因为传说中的“assign"问题WA了一次。。。

    EASY!!!

    庆祝41题!冲向50!!

  • 0
    @ 2009-06-21 19:21:41

    背包变种!

    #include

    int d[401][401]={0};

    int main()

    {

    int i,j,k,V,M,n;

    int v[51],m[51],h[51];

    scanf("%d%d%d",&V,&M,&n);

    for(i=0;i=m[i];k--)

    d[j][k]=(d[j-v[i]][k-m[i]]+h[i]>d[j][k]?d[j-v[i]][k-m[i]]+h[i]:d[j][k]);

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

    return 0;

    }

  • 0
    @ 2009-05-30 19:08:29

    这也敢叫难度2??

  • 0
    @ 2009-05-30 16:23:41

    f[j,k]:=max(f[j,k],f[j-a[i],k-b[i]]+c[i]);

  • 0
    @ 2009-05-26 15:45:25

    program lc;

    var

    ma,w,r,n:longint;

    v,m,c:array[1..500] of longint;

    f:array[0..51,0..401,0..401] of longint;

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

    begin

    if a>b then max:=a else max:=b;

    end;

    procedure init;

    var

    i:longint;

    begin

    readln(w,r);

    readln(n);

    for i:=1 to n do

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

    end;

    procedure dp;

    var

    i,j,k:longint;

    begin

    for i:=1 to n do

    for j:=v[i] to w do

    for k:=m[i] to r do

    begin

    f:=max(f,f+c[i]);

    if f>ma then ma:=f;

    end;

    end;

    begin

    init;

    dp;

    writeln(ma);

    end.

    编译通过...

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

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

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

    ├ 测试数据 04:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 05:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 06:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 07:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 08:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 09:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 10:答案错误... ├ 标准行输出

     ├ 错误行输出

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

    Unaccepted 有效得分:30 有效耗时:0ms

    这是怎么回事?

  • 0
    @ 2009-05-22 15:34:58

    const maxn=401;

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

    a,b,c,l,i,j,n,m:longint;

    begin

    readln(n,m);

    readln(l);

    for l:=1 to l do begin

    readln(a,b,c);

    for i:=n downto a do

    for j:=m downto b do

    if f+c>fthen

    f:=f+c;

    end;

    writeln(f[n,m]);

    end.

  • 0
    @ 2009-05-08 17:39:41

    二维费用的01背包,只是多了一层循环而已

  • 0
    @ 2009-05-03 16:03:32

    max{f,f+p[i]}

    j是>=v[i]的

    h是>=w[i]的

    注意下。。。不然740那组会输出700

    教训!

  • 0
    @ 2009-05-01 14:59:03

    puppy就是好啊,最笨的方程也0ms:

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    是有2个“背包容量”的01背包,

    最笨的动态转移方程如下:(遇上6k就是人品问题啦!!等puppy吧!!!)

    f:=

    max{f,f+p[i]}

    超时的别骂我·······

  • 0
    @ 2009-04-11 23:54:04

    #include

    using namespace std;

    int f[400][400],V,M,N,v[50],m[50],w[50];

    int main()

    {

    cin >> V >> M >> N;

    for(int i = 0;i < N;i++) cin >> v[i] >> m[i] >> w[i];

    for(int i = 0;i < N;i++)

    for(int vi = V;vi >= v[i];--vi)

    for(int mi = M;mi >= m[i];--mi)

    {

    if(i == 0) f[vi][mi] = w[i];

    else f[vi][mi] = max(f[vi-v[i]][mi-m[i]]+w[i],f[vi][mi]);

    }

    cout

  • 0
    @ 2009-04-11 23:35:58

    so easy的二维背包,就是加了个限制条件,判断条件是< > 号千万别反了,我就是因为这个重交了好几次。。。。。

    貌似我这个没有0ms,似乎有待优化~

    f[vi][mi][i] = max(f[vi-v[i]][mi-m[i]]+w[i],f[vi][mi]);

  • 0
    @ 2009-04-01 20:18:07

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    program ma;

    var

    v,m,n,i,j,k:longint;

    a,b,c:array[1..10000] of longint;

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

    begin

    readln(v,m);

    readln(n);

    for i:=1 to n do

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

    for i:=1 to n do

    begin

    for j:=v downto a[i] do

    for k:=m downto b[i] do

    if f[j-a[i],k-b[i]]+c[i]>f[j,k] then

    f[j,k]:=f[j-a[i],k-b[i]]+c[i];

    end;

    write(f[v,m]);

    end.

    二维01背包……

    终于破百了……101题……

    庆祝下……

信息

ID
1334
难度
2
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
2916
已通过
1743
通过率
60%
被复制
5
上传者