问题描述
一种双核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位恢复原始数据维度)。
网友评论