双核处理

问题描述

一种双核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位恢复原始数据维度）。