CPU双核调度问题

问题：一种双核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

咋一看，小白的我很是懵逼，所以网上搜索了一波。以下就是我的小结。

首先，我们从01背包问题开始。所谓01背包问题（可参考博客：http://www.cnblogs.com/zhangcaiwang/p/6651530.html），就是一共有n个宝石 和一个容量为C的背包。把n个宝石排成一排并编上号： 0,1,2,…,n-1。第i个宝石对应的体积和价值分别为V[i]和W[i] 。背包总共也就只能装下体积为C的东西，那要装下哪些宝石才能让我获得最大的利益呢？

一般遇到n，你就果断地给n赋予一个很小的数， 比如n=3。然后设背包容量C=10，三个宝石的体积为5，4，3，对应的价值为20，10，12。 对于这个例子，我想智商大于0的人都知道正解应该是把体积为5和3的宝石装到背包里， 此时对应的价值是20+12=32。接下来，我们把第三个宝石拿走， 同时背包容量减去第三个宝石的体积（因为它是装入背包的宝石之一）， 于是问题的各参数变为：n=2，C=7，体积｛5，4｝，价值｛20，10｝。好了， 现在这个问题的解是什么？我想智商等于0的也解得出了：把体积为5的宝石放入背包 （然后剩下体积2，装不下第二个宝石，只能眼睁睁看着它溜走），此时价值为20。 这样一来，我们发现，n=3时，放入背包的是0号和2号宝石；当n=2时， 我们放入的是0号宝石。这并不是一个偶然，没错， 这就是传说中的“全局最优解包含局部最优解”（n=2是n=3情况的一个局部子问题）。 绕了那么大的圈子，你可能要问，这都哪跟哪啊？说好的状态呢？说好的状态转移方程呢？ 别急，它们已经呼之欲出了。

我们再把上面的例子理一下。当n=2时，我们要求的是前2个宝石， 装到体积为7的背包里能达到的最大价值；当n=3时，我们要求的是前3个宝石， 装到体积为10的背包里能达到的最大价值。有没有发现它们其实是一个句式！OK， 让我们形式化地表示一下它们， 定义d(i,j)为前i个宝石装到剩余体积为j的背包里能达到的最大价值。 那么上面两句话即为：d(2, 7)和d(3, 10)。这样看着真是爽多了， 而这两个看着很爽的符号就是我们要找的状态了。 即状态d(i,j)表示前i个宝石装到剩余体积为j的背包里能达到的最大价值。 上面那么多的文字，用一句话概括就是：根据子问题定义状态！你找到子问题， 状态也就浮出水面了。而我们最终要求解的最大价值即为d(n, C)：前n个宝石 （0,1,2…,n-1）装入剩余容量为C的背包中的最大价值。状态好不容易找到了， 状态转移方程呢？顾名思义，状态转移方程就是描述状态是怎么转移的方程（好废话！）。 那么回到例子，d(2, 7)和d(3, 10)是怎么转移的？来，我们来说说2号宝石 （记住宝石编号是从0开始的）。从d(2, 7)到d(3, 10)就隔了这个2号宝石。 它有两种情况，装或者不装入背包。如果装入，在面对前2个宝石时， 背包就只剩下体积7来装它们，而相应的要加上2号宝石的价值12， d(3, 10)=d(2, 10-3)+12=d(2, 7)+12；如果不装入，体积仍为10，价值自然不变了， d(3, 10)=d(2, 10)。记住，d(3, 10)表示的是前3个宝石装入到剩余体积为10 的背包里能达到的最大价值，既然是最大价值，就有d(3, 10)=max{ d(2, 10), d(2, 7)+12 }。好了，这条方程描述了状态d(i, j)的一些关系， 没错，它就是状态转移方程了。把它形式化一下：d(i, j)=max{ d(i-1, j), d(i-1,j-V[i-1]) + W[i-1] }。注意讨论前i个宝石装入背包的时候， 其实是在考查第i-1个宝石装不装入背包（因为宝石是从0开始编号的）。至此， 状态和状态转移方程都已经有了。接下来，直接上代码。

for(int i=0; i<=n; ++i){  
    for(int j=0; j<=C; ++j){  
        d[i][j] = i==0 ? 0 : d[i-1][j];  
        if(i>0 && j>=V[i-1]) 
        	//d[i][j] >?= d[i-1][j-V[i-1]]+W[i-1]
        	d[i][j] = d[i][j]>=(d[i-1][j-V[i-1]]+W[i-1])?d[i][j]:(d[i-1][j-V[i-1]]+W[i-1]);  
    }

看图可知：d[1][5]=20即前1个宝石（0号宝石）装到剩余体积为5的背包里能达到的最大价值显然是20；

d[2][4]=10即前2个宝石（0号、1号宝石）装到剩余体积为4的背包里能达到的最大价值显然是10，但如果d[2][5]=20，即前2个宝石（0号、1号宝石）装到剩余体积为5的背包里能达到的最大价值显然是20；

说了这么多，显然核心代码的流程大家应该清楚了。

说道这里，大家会很难理解，这01背包问题怎么和双核调度问题相关？

1.双核调度问题实质是动态规划问题，把数组分成两部分，使得两部分的和相差最小。

差值最小就是说两部分的和最接近，而且各部分的和与总和的一半也是最接近的。假设用sum1表示第一部分的和，sum2表示第二部分的和，SUM表示所有数的和，那么sum1+sum2=SUM。假设sum1<sum2 那么SUM/2-sum1 = sum2-SUM/2; 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int num = 0;
		Scanner scanner = new Scanner(System.in);
		num = Integer.valueOf(scanner.nextLine());
		String[] strings = scanner.nextLine().split(" ");
		int[] task = new int[num];
		int sum = 0;
		for (int i = 0; i < num; i++) {
			task[i] = Integer.valueOf(strings[i]) / 1024;
			sum += task[i];
		}
		int[][] handler = new int[num + 1][sum / 2 + 1];
		for (int i = 0; i <= num; i++)
			for (int j = 0; j <= sum / 2; j++) {
				handler[i][j] = i == 0 ? 0 : handler[i - 1][j];
				if (i > 0 && j >= task[i - 1])
					//handler[i][j]：用前i个物体装容量为j的背包能够装下的最大值
					//handler[i - 1][j - task[i - 1]] + task[i - 1]:表示第i个物体装进背包的情况
					//handler[i - 1][j]:表示第i件物品不装进背包的情况
					handler[i][j] = Math.max(handler[i - 1][j],
							handler[i - 1][j - task[i - 1]] + task[i - 1]);
			}
		//两个处理器谁分的任务更多，以更多地算
		System.out.print(Math.max(handler[num][sum / 2], sum- handler[num][sum / 2]) * 1024);
	}
}

用题目数据为例：

很显然，这里面所谓单个“宝石”的体积是数的大小（1024 的倍数），可以说是1。背包容量就是横着的蓝条（不断递增），而所谓的“宝石”价值也是数的大小（1024 的倍数）。

说白了，这里的“宝石的单位价值”是1.

小结：

核心代码虽短，却很绕。但只要记住，背包问题是固定的体积V，使得背包中宝石的价值最大，而双核处理问题，固定的sum1处理数量,使得sum1尽可能大，以至于接近1/2.

最后

以上就是从容石头为你收集整理的CPU双核调度问题的全部内容，希望文章能够帮你解决CPU双核调度问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。