题目描述
一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。
输入例子:
5
3072 3072 7168 3072 1024
输出例子:
9216
思路
将问题转化为：求所有输入的数据中，累加最接近输入的总和的一半的结果，那么最少时间就是总和减去这个最接近一半的累加和
即：mid = sum/2。求累加和最接近mid的值为多少。
转化为了经典的背包问题
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
int sum = 0;
for(int i = 0; i < nums.length; i++) {
nums[i] = scanner.nextInt()/1024;
sum += nums[i];
}
int mid = sum/2;
int[] dp = new int[mid+1];
for(int i = 0; i < nums.length; i++) {
int tmp = nums[i];
for(int j = mid; j >= 0; j--) {
if(tmp <= j) {
dp[j] = Math.max(dp[j], dp[j-tmp]+tmp);
}else {
break;
}
}
}
System.out.println(1024*sum - dp[mid]*1024);
}
}
|
考差点