问题描述
一种双核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
- 将数据右移了10位，减少数据的维度，防止状态数过多；
- 最后的最小时间为两个CPU时间的最大值，应为(sum - dp[sum / 2]) << 10（左移10位恢复原始数据维度）。
