HDU 1171(完全背包)

蔚落 2022-09-20 11:23 147阅读 0赞

题意：给一个数n，接下来n行，每行对应一个设备的两个值，第一个为设备的价值，第二个为该设备的数量。如何把所有设备一分为二，求两部分的价值总和尽量接近。

#include <cstdio>
    #include <cstring>
    
    int W[59], M[59];
    int F[295000];
    #define _max(a, b) ((a) > (b) ? (a) : (b))
    int main()
    {
        //freopen("1.txt", "r", stdin);
        //freopen("2.txt", "w", stdout);
        int n, i, s, ave;
        while (scanf("%d", &n) != EOF && n > 0)
        {
            for (s = i = 0; i < n; ++i)
                scanf("%d%d", W+i, M+i), s += M[i]*W[i];
            ave = s / 2;
            memset(F, 0, sizeof(int) * (ave+1));
            for (i = 0; i < n; ++i)
            {
                int k = 1;
                while (k < M[i])
                {
                    for (int v = ave; v >= k*W[i]; --v)
                        F[v] = _max(F[v], F[v-k*W[i]]+W[i]*k);
                    M[i] = M[i] - k;
                    k = 2*k;
                }
                for (int v = ave; v >= M[i]*W[i]; --v)
                    F[v] = _max(F[v], F[v-M[i]*W[i]]+W[i]*M[i]);
            }
            printf("%d %d\n", s - F[ave], F[ave]);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1171(完全背包)

题意：给一个数n，接下来n行，每行对应一个设备的两个值，第一个为设备的价值，第二个为该设备的数量。如何把所有设备一分为二，求两部分的价值总和尽量接近。 incl

蔚落/ 2022年09月20日 11:23/ 0 赞/ 148 阅读

相关 HDU 1114（完全背包）

题意：给出小猪钱罐空时的重量E，满时的重量F，钱币的种类N，接下来N行，分别为p w，p为钱币价值，w为钱币重量，求钱罐中钱币的最小价值。 include <c

╰+攻爆jí腚メ/ 2022年09月20日 11:17/ 0 赞/ 119 阅读

相关 HDU 2159-FATE(完全背包)

FATE Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

客官°小女子只卖身不卖艺/ 2022年07月24日 06:14/ 0 赞/ 93 阅读

相关 hdu 1171 - Big Event in HDU(完全背包)

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=1171][http_acm.hdu.edu.cn_showproblem.p

待我称王封你为后i/ 2022年07月12日 08:12/ 0 赞/ 81 阅读

相关 hdu 1171 - Big Event in HDU(完全背包)

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=1171][http_acm.hdu.edu.cn_showproblem.p

你的名字/ 2022年07月12日 08:12/ 0 赞/ 79 阅读

相关 01背包+完全背包 HDU - 5410 

Today is CRB's birthday. His mom decided to buy many presents for her lovely son. S

喜欢ヅ旅行/ 2022年06月17日 09:27/ 0 赞/ 153 阅读

相关 HDU 2159(动态规划-完全背包)

问题描述: 最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现

桃扇骨/ 2022年06月06日 06:59/ 0 赞/ 160 阅读

相关 Piggy-Bank-HDU1114-完全背包

Piggy-Bank Problem Description Before ACM can do anything, a budget must be p

不念不忘少年蓝@/ 2022年06月05日 05:56/ 0 赞/ 113 阅读

相关 HDU 1171 Big Event in HDU [多重背包]

include <stdio.h> include <string.h> include <math.h> include <algorithm

分手后的思念是犯贱/ 2022年05月29日 10:24/ 0 赞/ 117 阅读

相关【HDU 2159】FATE（完全背包）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2159][http_acm.hdu.edu.cn_showproblem.ph

落日映苍穹つ/ 2022年02月15日 07:53/ 0 赞/ 174 阅读