首页 > 试题广场 >

双核处理

[编程题]双核处理
  • 热度指数：11768 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述:
输入包括两行： 第一行为整数n(1 ≤ n ≤ 50) 第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。


输出描述:
输出一个整数，表示最少需要处理的时间
示例1

输入

5 3072 3072 7168 3072 1024

输出

9216
算法知识视频讲解
添加回答
Java
詆調壹點头像 詆調壹點 
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int[] arr = new int[n];
			int sum = 0;
			for (int i = 0; i < arr.length; i ++) {
				arr[i] = sc.nextInt() >> 10;
				sum += arr[i];
			}
			// dp[j]表示在容量为j的情况下可存放的重量
			// 如果不放arr[i]重量为dp[j],如果放arr[i]重量为dp[j-arr[i]]+arr[i];
			int[] dp = new int[sum / 2 + 1];
			for (int i = 0; i < n; i ++) {
				for (int j = sum / 2; j >= arr[i]; j --) {
					dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
				}
			}
			System.out.println(Math.max(dp[sum / 2], sum - dp[sum / 2]) << 10);
		}
	}
}

编辑于 2017-04-10 14:08:37 回复(20)
Glenn_Gould头像 Glenn_Gould 
# include <iostream>
# include <vector>
using namespace std;
const int mul=1024;
int main()
{
    int n=0,total_len=0;
    cin>>n;
    vector<int> vi(n,0);
    for(int i=0;i<n;i++) {
       cin>>vi[i];
       vi[i]/=mul;
       total_len+=vi[i];
    }
    int dp_len=total_len/2;
    vector<int> dp(dp_len+1,0);
    for(int i=0;i<n;i++) {
        for(int j=dp_len;j>=vi[i];j--) {
            dp[j]=max(dp[j],dp[j-vi[i]]+vi[i]);
        }
    }
    int ret=(total_len-dp[dp_len])*mul;
    cout<<ret;
    return 0;
}

发表于 2017-08-02 14:57:20 回复(5)
我的兄弟叫卷头像 我的兄弟叫卷
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);    
        while(sc.hasNext()) {
        int n=sc.nextInt();
        int[] cpu=new int[n];
        int sum=0;
        for(int i=0;i<n;i++){
            cpu[i]=sc.nextInt()/1024;
            sum+=cpu[i];
        }
        int sumhalf=sum/2;
        int[] time=new int[sum+1];
        for(int i=0;i<cpu.length;i++){
            for(int j=sumhalf;j>=0;j--){
                if(j>=cpu[i])    time[j]=Math.max(time[j], time[j-cpu[i]]+cpu[i]);
            }
        }
        System.out.println(Math.max(time[sumhalf], sum-time[sumhalf])*1024);
        }
    }
}
发表于 2017-03-26 09:45:47 回复(20)
☠头像 ☠
### 分析
题意很清晰，就是给一个数组，要我们把他分成两份并分别求和，使得这两个和的最大值最小。
我下意识的想法是枚举出所有有可能的和，但是复杂度大概是$O(2^n)$，貌似会超时。可是仔细一看，$length[i]$的取值在$[1,4096]$之间，那么最多n个数的和的范围肯定在$[n,4096n]$之间。那么我们只要对能取到的和打个表，而且表的长度肯定不超过$4096*50=204800$，再加上总共遍历n遍，计算量大概是1e7的级别，可解。

### 我的答案
```cpp
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int n;
int a[51];
set<int>s;
int sum=0;
int main(){
cin>>n;
for(int i=0;i<n;i++){
int tmp;
cin>>tmp;
a[i]=tmp/1024;
sum+=a[i];
}
s.insert(0);
for(int i=0;i<n;i++){
set<int>added;
for(set<int>::iterator it=s.begin();it!=s.end();it++){
added.insert(*it+a[i]);
}
s.insert(added.begin(),added.end());
}
int ans=sum;
for(set<int>::iterator it=s.begin();it!=s.end();it++){
ans=min(ans,max(*it,sum-*it));
}
cout<<ans*1024<<endl;
}
```
https://blog.mythsman.com/2017/03/31/1/#双核处理
编辑于 2017-03-31 13:06:43 回复(3)
Hell0123头像 Hell0123
Python TLE
我觉得代码已经不能再优化了。 
import sys

if __name__ == '__main__':
    line = sys.stdin.readline()
    n = int(line)
    nums = [int(t)//1024 for t in sys.stdin.readline().split()]
    allnum = sum(nums)
    half = allnum//2
    values = [0]*(half+1)
    for num in nums:
        for i in range(half, -1, -1):
            if i >= num:
                values[i] = max(values[i], values[i-num]+num)
    print((allnum-values[-1])*1024)

发表于 2017-03-28 15:12:18 回复(3)
JacobGo！头像 JacobGo！ 
package go.jacob.day912;

import java.util.Scanner;

public class Demo1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt() >> 10;
			sum += arr[i];
		}
		int[][] res = new int[n + 1][sum / 2 + 1];

		for (int i = 0; i < n; i++) {
			for(int j=sum/2;j>=0;j--){
				if(j>=arr[i]){
					res[i+1][j]=Math.max(res[i][j], res[i][j-arr[i]]+arr[i]);
				}else{//else条件必须有
					res[i+1][j]=res[i][j];
				}
			}
			/*for (int j = 0; j < sum / 2; j++) {
				if (j + 1 >= arr[i]) {
					res[i + 1][j + 1] = Math.max(res[i][j + 1], res[i][j + 1 - arr[i]] + arr[i]);
				}
			}*/
		}
		System.out.println(Math.max(res[n][sum / 2], sum - res[n][sum / 2]) << 10);
		sc.close();
	}
}


发表于 2017-09-12 20:50:02 回复(0)
Java
YiBuLZ头像 YiBuLZ 
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

/**
 * Created by YiBuLZ on 2017/4/7 0007.
 */
public class Main {
    public static void main(String[] args) {
        //以下处理输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i ++) {
            arr[i] = sc.nextInt();
        }
        sc.close();
        //处理输入ok

        //先对数组 排序 从大到小排序，为了使这个方法能用，将
        //Integer[] arr = new Integer[n]; 如果是int，会报错
        Arrays.sort(arr, Collections.reverseOrder());

        if (n <= 0) {
            return;
        }
        if (n == 1) {
            System.out.println(arr[0]);
            return;
        }

        if (n >= 2) {
            int cpu1 = arr[0];
            int cpu2 = arr[1];
            for (int i = 2; i < n; i ++) {
              if (cpu1 > cpu2) {
                  cpu2 += arr[i];
              } else {
                  cpu1 += arr[i];
              }
            }
            System.out.println(Math.max(cpu1, cpu2));
        }
    }
}
   请问，如果不用背包方法去做，用以上方法去处理，问题出在哪里？

您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为50.00%

测试用例:
10
1411072 2110464 1388544 2362368 1103872 59392 133120 1184768 1500160 1332224

对应输出应该为:

6295552

你的输出为:

6317056

发表于 2017-04-08 10:48:54 回复(9)
牛客7142391号头像 牛客7142391号 

	#include <iostream>





	#include <algorithm>





	using namespace std;





	





	int main()





	{





	int n;





	cin >> n;





	int *length = new int [n];





	int curData, sum = 0, half = 0;





	for (int i = 0; i < n; i++) {





	cin >> curData;





	length[i] = curData / 1024;





	sum = sum + length[i];





	}





	half = sum / 2;





	sort(length, length + n);





	// 构建二维数组





	int **a = new int *[n];





	for (int i = 0; i < n; i++) {





	a[i] = new int [half];





	}





	





	// 填写二维数组





	for (int i = 0; i < half; i++) {





	for (int j = n -1; j >= 0; j--) {





	// 最后一行





	if (j == n-1 ) {





	if (i+1 >= length[j]) {





	a[j][i] = length[j];





	}





	} else {





	if ( i+1 >= length[j] ) {





	a[j][i] = max(a[j+1][i],(length[j] + a[j+1][i-length[j]]));





	} else {





	a[j][i] = a[j+1][i];





	}





	}





	}





	}





	





	cout << (sum - a[0][half - 1]) * 1024;





	





	return 0;





	}

发表于 2017-03-28 14:54:06 回复(0)
牛客375006号头像 牛客375006号

这是一个01背包问题的变形，其中value[n]应设置为与weight[n]相同的数组，故设置同一个数组w[n]来指代它们。

另外下述代码使用一维迭代数组优化了空间复杂度。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int w[n], C = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        long temp;
        cin >> temp;
        w[i] = (int)(temp / 1024);
        sum += w[i];
    }
    C = sum / 2;
    int f[C + 1];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; i++) {
        for (int j = C; j >= w[i]; j--) {
            f[j] = max(f[j], f[j - w[i]] + w[i]);
        }
    }
    cout << 1024 * (sum - f[C]);
    return 0;
}
发表于 2017-10-24 03:52:21 回复(1)
Python
charles7头像 charles7 
n = input()
length =[int(i)//1024 for i in input().strip().split()] 

half = sum(length)/2
h = set(length) 
 
for i in length: 
	for j in list(h): 
 		h.add(i+j)  
 
h = [i for i in h if i>=half] 
 
print(min(h)*1024)

发表于 2017-08-09 01:17:18 回复(0)
🌸cassie西头像 🌸cassie西
  • 本地可以运行，OJ显示段错误：不知是为何。。请大家指教
  • 题目理解为：将子数组分成两份，其和的绝对值最小，输出较大和。
    • 用01 背包的思想。在数组中选出最优子数组，其和不超过总和一半的。total/2
    • d[i][j] 表示总容量为j，取前i个数的最大总和。w[i]表示重量和价值（背包）
    • d[i][0]=d[0][j]=0
    • 当j<w[i]，d[i][j]=d[i-1][j]
    • 当j>=w[i],d[i][j]=max(d[i-1][j],d[i-1][j-w[i]]+w[i]) 
#include 
using namespace std;

int main() {//01背包

    int n=0;
    while (scanf("%d",&n)!=EOF) {//输入一个数字n
        int w[50]={0};
        int total = 0;
        int res =0;

        for(int i =0 ;i<n;i++){//输入一个数组w
            cin>>w[i];
            w[i]/=1024;
            total+=w[i];//!!
        }
        total /=2;//最大价值，双核分两组，绝对值差越小越好，时间小的那组越接近于sum／2

        int d[n][total];//d[i][j] 背包容量为j，前i个数的最大和
        for(int i=0;i<n;i++){
            for (int j=0 ; j<total; j++) {
                if( (i==0)||(j==0)){
                    d[i][j]=0;
                }else if (j< w[i]){
                    d[i][j] = d[i-1][j];
                }else{
                    d[i][j]= max(d[i-1][j],d[i-1][j-w[i]]+w[i]);
                }
            }
        }
        res = d[n-1][total-1];
        res = (total*2-res)*1024;
        cout<<res<<endl;    
    }
    return 0;
}
发表于 2017-08-02 22:16:45 回复(0)
萧草尤头像 萧草尤 
//C++就是简单的一个背包问题，背包总量为sum/2,最终结果就是求sum - dp[sum / 2], dp[sum / 2]
的最大值 #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(void)
{
	int num;
	while (cin >> num)
	{
		vector<int> vec1;
		int numsingle,sum=0;
		for (int i = 0; i < num; i++)
		{
			cin >> numsingle;
			vec1.push_back(numsingle/1024);
			sum += numsingle / 1024;
		}
		int *dp = new int[sum / 2 + 1]{0};
		for (int i = 0; i < num; i++)
		{
			for (int j = sum / 2; j >= vec1[i]; j--)
			{
				dp[j] = max(dp[j], dp[j - vec1[i]] + vec1[i]);
			}
		}
		cout << max(sum - dp[sum / 2], dp[sum / 2])*1024 << endl;
	}
	system("pause");
	return 0;
}

python 也是同样做法，但是却超时了，不明所以 import sys

if __name__ == '__main__':
        line=sys.stdin.readline()
        n=int(line)
        nums=[int(t)//1024 for t in sys.stdin.readline().split()]
        allnum=sum(nums)
        half=allnum//2
        values=[0]*(half+1)
        for num in nums :
                for i in range(half,num-1,-1):
                        values[i]=max(values[i],values[i-num]+num)
        print(max(values[half]*1024,(allnum - values[half])*1024))


编辑于 2017-07-28 10:42:41 回复(1)
496头像 496 
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
 
int dp(vector<int> lengths,int half){
    int row = lengths.size();
    int col = half;
    vector<vector<int>> res(row+1,vector<int>(col+1,0));
    for(int i=1;i<=row;i++)
        for(int j=1;j<=col;j++){
            if(j>=lengths[i-1])
                res[i][j] = max((res[i-1][j-lengths[i-1]]+lengths[i-1]),res[i-1][j]);
            else
                res[i][j] = res[i-1][j];
        }
    return res[row][col];
}
 
int main(){
    int n;
    vector<int> lengths;
    //lengths.push_back(0);
    cin>>n;
    int sum = 0;
    for(int i=0;i<n;i++){
        int num;
        cin>>num;
        lengths.push_back(num/1024);
        sum += num/1024;
    }
    int half = sum/2;
    //转化成0-1背包问题
    cout<<(sum-dp(lengths,half))*1024<<endl;
}

发表于 2017-07-21 09:49:43 回复(0)
sun1035头像 sun1035
将所有任务排序，耗时高的任务优先进入空闲核，返回处理时间较长的核的处理时间
发表于 2017-05-05 09:01:19 回复(8)
Python
周昆头像 周昆 
N = int(raw_input())
length = map(lambda x: int(x)//1024, raw_input().split())
V = sum(length) // 2
f = [0] * (V + 1)
for i in range(N):
	v = V
	while v >= length[i]:
		f[v] = max(f[v-length[i]] + length[i], f[v])
		v = v - 1
print max(f[V], sum(length) - f[V]) * 1024 


强烈建议每一种语言有自己的时间时限。Python这个已经不知道还能怎么再优化了。
目前能通过40%。 希望能有人能给出更精简的code
编辑于 2017-04-11 17:30:21 回复(2)
一个小菜鸡头像 一个小菜鸡
思想理解：完成所有n个任务需要sum时间，放入两个cpu中执行，假设第一个cpu处理时间为n1，第二个cpu时间为sum-n1，并假设n1 <= sum/2，sum-n1 >= sum/2，要使处理时间最小，则n1越来越靠近sum/2，最终目标是求max（n1，sum-n1）的最大值。
转换为01背包问题：已知最大容纳时间为sum/2，有n个任务，每个任务有其的完成时间，求最大完成时间。 
public class Main {
    public static int getMax(int[] packTime, int n, int maxTime){
        //bestTime[i][j]表示最大时间下的完成第i个任务所需的时间int[][] bestTime = new int[n+1][maxTime+1];for(int j = 0; j <= maxTime; j++ ){
            //能容纳最大时间为j
            for(int i = 0; i <= n; i++){
                //当完成0个任务或者最大时间为0时，时间为0
                if(i == 0 || j == 0) {
                    bestTime[i][j] = 0;
                }
                //当容纳最大时间小于单独完成第i件任务时间，则为前n-1完成任务时间总和
                else if(j < packTime[i-1]){
                    bestTime[i][j] = bestTime[i-1][j];
                }
                //完成第i件任务时，两种情况：取最大值
                //1.超过容纳最大时间，则为bestTime[i-1][j];
                //2.没超过，则为bestTime[i-1][j-packTime[i-1]]+packTime[i-1])
                //上述表示为在完成第i件任务时所需时间为bestTime[i-1][j-packTime[i-1]]，然后在加上第i个任务时间为packTime[i-1]
                else{bestTime[i][j] = Math.max(bestTime[i-1][j], bestTime[i-1][j-packTime[i-1]]+packTime[i-1]);}
            }
        }
        return bestTime[n][maxTime];
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] packTime = new int[n];
        int sum = 0;
        for(int i = 0; i < n; i++){
            packTime[i] = sc.nextInt()/1024;
            sum += packTime[i];
        }
        int half = sum/2;
        int res = getMax(packTime, n, half);
        System.out.println(Math.max(res, sum-res)*1024);
    }
}

发表于 2017-03-30 09:58:00 回复(4)
Python
Fzldq头像 Fzldq
Python细节：两者比较不要用max，用main包一下会快很多，剪枝 
def main():
    n = int(input())
    lst = list(map(lambda x: int(x) >> 10, input().split()))

    s = sum(lst) // 2
    dp = [0] * (s + 1)
    for i in range(n):
        for j in range(s, -1, -1):
            if j >= lst[i]:
                tmp = dp[j - lst[i]] + lst[i]
                if dp[j] < tmp:
                    dp[j] = tmp
            else:
                break
    print(max(dp[s], sum(lst) - dp[s]) << 10)


if __name__ == '__main__':
    main()


编辑于 2020-07-18 01:49:54 回复(0)
C/C++
相见欢、头像 相见欢、 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
int sum = 0;
cin >> n;
vector<int> f(n);
for(int i=0;i<n;i++){
cin >> f[i];
f[i] /=1024;
sum += f[i];
}
vector<vector<int>> dp(n+1,vector<int>(sum/2,0));
for(int i = 1;i<=n;i++)
{
for(int j=1;j<=sum/2;j++)
{
dp[i][j] = dp[i-1][j];
if(f[i-1]<=j)
dp[i][j] = max(dp[i][j],dp[i-1][j-f[i-1]]+f[i-1]);
}
}
cout << (sum-dp[n][sum/2])*1024;

}


编辑于 2020-06-13 22:00:28 回复(0)
为啥要起名字头像 为啥要起名字 
n=int(raw_input())
s=list(map(int,raw_input().strip().split()))
h=set(s)
for i in s:
    for j in list(h):
        h.add(i+j)
h=[i for i in h if i>=sum(s)//2]
print(min(h))

动态规划
n=int(raw_input())
l=[int(i)/1024 for i in raw_input().strip().split()]
sumNum=sum(l)
m=sumNum//2
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if j<l[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i-1]]+l[i-1])
print((sumNum-dp[n][m])*1024)  您的代码已保存 内存超限:您的程序使用了超过限制的内存 case通过率为50.00%

编辑于 2018-07-28 17:37:59 回复(0)
逗比请来的猴子头像 逗比请来的猴子 
import java.util.Scanner;


/*
 * 参考大神的解题思路：https://www.nowcoder.com/questionTerminal/9ba85699e2824bc29166c92561da77fa?orderByHotValue=1&difficulty=11110&page=1&onlyReference=false
 *
 * 尽可能使两个cpu执行的任务总和相差最小，能够想到转换成容量为sum/2的背包问题也是牛逼了；
 * 设置sum/2大小的背包，然后针对所欲的货物大小更新所能够容纳的最大容量
 * */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] nums = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
//                缩小容量空间
                nums[i] = scanner.nextInt() >> 10;
                sum += nums[i];
            }
            int[] dp = new int[sum / 2 + 1];
            for (int i = 0; i < n; i++) {
                for (int j = sum / 2; j >= nums[i]; j--) {
//                    对每件货物，更新能够获取的最大值
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
            int tmp = dp[sum / 2];
            System.out.println((tmp > sum - tmp ? tmp : sum - tmp) << 10);
        }
    }
}
添加笔记
发表于 2018-04-11 20:28:11 回复(0)
提交观点

问题信息

动态规划
来自：网易2017春招笔试真...
难度：
61条回答 22348浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号