美文网首页
双核处理

双核处理

作者: RobotBerry | 来源:发表于2017-04-24 14:46 被阅读0次

    问题描述

    一种双核CPU的两个核能够同时的处理任务,现在有n个已知数据量的任务需要交给CPU处理,假设已知CPU的每个核1秒可以处理1kb,每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理,现在需要设计一个方案让CPU处理完这批任务所需的时间最少,求这个最小的时间。

    输入描述

    输入包括两行:
    第一行为整数n(1 ≤ n ≤ 50)
    第二行为n个整数length[i],1024 ≤ length[i] ≤ 4194304,表示每个任务的长度为length[i]kb,每个数均为1024的倍数。

    输出描述

    输出一个整数,表示最少需要处理的时间

    输入例子

    5
    3072 3072 7168 3072 1024

    输出例子

    9216

    分析: 当两个CPU的任务时间一样时,总时间最小。所以要使总时间最小,就要让两个CPU的任务时间差距最小。故可以将本问题转化成01背包问题:每个任务的价值和重量都等于其时间,背包的总重量为总时间的一半,选择合适的任务将背包填得尽量满。

    代码

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        int n;
        scanf("%d", &n);
        vector<int> length(n);
    
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &length[i]);
            length[i] >>= 10;
            sum += length[i];
        }
    
        vector<int> dp(sum / 2 + 1, 0);
    
        for (int i = 0; i < n; i++)
        {
            for (int j = sum / 2; j >= 1; j--)
            {
                if (j >= length[i])
                {
                    dp[j] = max(dp[j], dp[j - length[i]] + length[i]);
                }
            }
        }
    
        printf("%d\n", (sum - dp[sum / 2]) << 10);
    
        return 0;
    }
    

    note

    1. 将数据右移了10位,减少数据的维度,防止状态数过多;
    2. 最后的最小时间为两个CPU时间的最大值,应为(sum - dp[sum / 2]) << 10(左移10位恢复原始数据维度)。

    相关文章

      网友评论

          本文标题:双核处理

          本文链接:https://www.haomeiwen.com/subject/qgfpzttx.html