首页 > 试题广场 >

双核处理

[编程题]双核处理

热度指数：11779 时间限制：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

输出

算法知识视频讲解

Java

卖萌の哈士奇

//将该问题转换为0/1背包问题,设总数为SUM,相当于是在大小为SUM/2的背包中,尽可能多的放入物品,
//每个物品的大小和价值均为N,最后用SUM减去该背包中的物品大小,即是答案 import java.util.*;  /**  * Created by meichen on 17-9-7  */ public class Main { public static void main(String[] args){
        Scanner in = new Scanner(System.in);  while (in.hasNext()){ int num = in.nextInt();  int sum = 0;  List<Integer> list = new ArrayList<Integer>();  for(int i = 0; i < num; i++){ int n = in.nextInt() / 1024;  sum += n;  list.add(n);  } int avg = sum / 2;  int[][] dp = new int[num + 1][avg + 1];  for(int i = 1; i <= avg; i++){ for(int j = 1; j <= num; j++){ if(i >= list.get(j - 1)){
                        dp[j][i] = Math.max(dp[j - 1][i],dp[j - 1][i - list.get(j - 1)] + list.get(j - 1));  }else {
                        dp[j][i] = dp[j - 1][i];  }

                }
            } int result = 1024 * (sum - dp[num][avg] > dp[num][avg] ? sum - dp[num][avg] : dp[num][avg]);  System.out.print(result);  }
    }
}

发表于 2017-09-07 16:55:54 回复(0)

Java

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)

Java

天弈

import java.util.*; public class Main { static Scanner in = new Scanner(System.in);  public static void main(String[] args) { fun1();  }  private static void fun1() { int n = in.nextInt();  int[] arr = new int[n];  int sum = 0;  for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt() / 1024;  sum += arr[i];  }  int knapsack = sum / 2;  int[][] bagMatrix = new int[n][knapsack + 1];  Arrays.sort(arr);  for (int i = n - 1; i >= 0; i--) { for (int j = 1; j <= knapsack; j++) { if (i == n - 1) {
                    bagMatrix[i][j] = j >= arr[i] ? arr[i] : 0;  } else if (j - arr[i] >= 0) {
                    bagMatrix[i][j] = max(bagMatrix[i + 1][j], bagMatrix[i + 1][j - arr[i]] + arr[i]);  } else {
                    bagMatrix[i][j] = bagMatrix[i + 1][j];  }
            }
        } int max = bagMatrix[0][knapsack];  System.out.println((sum - max) * 1024);  } private static int max(int a, int b) { return a > b ? a : b;  }
}

编辑于 2017-03-28 20:59:17 回复(1)

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)