網易2017實習筆試題-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的倍數。

輸出一個整數，表示最少需要處理的時間。

問題實質是動态規劃問題，把數組分成兩部分，使得兩部分的和相差最小。

如何将數組分成兩部分使得兩部分的和的差最小？參考部落格http://www.tuicool.com/articles/ZF73Af

思路：

內插補點最小就是說兩部分的和最接近，而且各部分的和與總和的一半也是最接近的。 假設用sum1表示第一部分的和，sum2表示第二部分的和，SUM表示所有數的和，那麼sum1+sum2=SUM。假設sum1<sum2 那麼SUM/2-sum1 = sum2-SUM/2;  是以我們就有目标了，使得sum1<=SUM/2的條件下盡可能的大。也就是說從n個數中選出某些數，使得這些數的和盡可能的接近或者等于所有數的和的一般。這其實就是簡單的 背包問題了：  背包容量是SUM/2. 每個物體的體積是數的大小，然後盡可能的裝滿背包。  dp方程：f[i][V] = max(f[i-1][V-v[i]]+v[i], f[i-1][V] )  f[i][V]表示用前i個物體裝容量為V的背包能夠裝下的最大值，f[i-1][V-v[i]]+v[i]表示第i個物體裝進背包的情況，f[i-1][V]表示第i件物品不裝進背包的情況。 

f[0][i]=0, f[j][0];
for(int i=1; i<n; ++i)
{
	for(j=1;j<SUM/2;++j)
	{
		f[i][j]=f[i-1][j];
		if(v[i]<=j && f[i-1][j-v[i]]+v[i] > f[i][j]);
		f[i][j]=f[i-1][j-v[i]]+v[i];
	}
}
           

最終內插補點就是SUM-2*f[n-1][SUM/2]; 

網易這道題的解法類似，由于數組元素是1024的倍數，是以先把每個數除以1024，求出總和。

#include <bits/stdc++.h>
using namespace std;
int dp[210000];
int n,arr[51];
int main()
{
    int n;
    scanf("%d",&n);
    int sum = 0;
    for(int i = 0 ; i < n ; i ++){
        scanf("%d",&arr[i]);
        arr[i] /= 1024;
        sum += arr[i];
    }
    for(int i = 0 ; i < n ; i ++)
        for(int j = sum/2 ; j >= arr[i] ; --j)
            dp[j] = max(dp[j],dp[j-arr[i]]+arr[i]);//dp[j]表示在容量為j的情況可存放的重量
    printf("%d\n",(sum-dp[sum/2])*1024);
    return 0;
}