双核处理(网易2017春招笔试题)

一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入包括两行： 第一行为整数n(1 ≤ n ≤ 50) 第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。 输出一个整数，表示最少需要处理的时间 这道题目实际上是一个01背包问题。

一个背包总容量为bagSize，现在有len个物品，第i个 物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

用一个数组f[i-1][j]表示在只有i-1个物品，容量为j的情况下背包问题的最优解，那么当物品种类变大为i时，最优解是什么？第i个物品可以选择放进背包或者不放进背包（这也就是0和1），假设放进背包（前提是放得下，即weight[i]<=j），那么f[i][j]=f[i][j-weight[i]+value[i]；如果不放进背包，那么f[i][j]=f[i-1][j]。

即状态转移方程：f[i][j]=max(f[i-1][j],f[i][j-weight[i]+value[i](weight[i]<=j))。

本题的代码如下：

#include<iostream> #include<algorithm> using namespace std; int Get01PackageAnswer(int *weight,int *value,int len,int bagSize); int main() { int len; cin >> len; int arr[50] = { 0 }; int tmp; int sum = 0; for (int i = 0; i < len; i++) { cin >> tmp; arr[i] = tmp / 1024; sum += arr[i]; } int bagSize = sum / 2; int maxTime = Get01PackageAnswer(arr,arr,len,bagSize); cout << max(maxTime, sum - maxTime) * 1024; return 0; } int Get01PackageAnswer(int *weight, int *value, int len, int bagSize) { int **f = new int*[len+1]; for (int i = 0; i < len+1; i++) { f[i] = new int[bagSize+1]; } for (int j = 0; j <= bagSize; j++) { for (int i = 0; i <= len; i++) { if (i == 0 || j == 0) { f[i][j] = 0; } else if (j < weight[i-1]) { f[i][j] = f[i-1][j]; } else { f[i][j] = max((f[i-1][j-weight[i-1]]+value[i-1]),(f[i-1][j])); } } } return f[len][bagSize]; }