问题描述：
一种双核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
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int count=sc.nextInt();
int[] length=new int[count];
int weight=0;
for(int i=0;i<count;i++){
int temp=sc.nextInt()/1024;
length[i]=temp;
weight+=temp;
}
int tmpResult=backbag(weight/2,length);
System.out.println(Math.max(weight-tmpResult,tmpResult)*1024);
}
public static int backbag(int m,int[] w){
int[] dp=new int[m+1];
for(int i=0;i<w.length;i++){
for(int j=m;j>=w[i];j--){
dp[j]=Math.max(dp[j],dp[j-w[i]]+w[i]);
}
}
return dp[m];
}
}
典型的背包问题，就不多解释了哈，。。。没优化的代码也贴上吧
import java.util.Scanner;
public class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int count=sc.nextInt();
int[] w=new int[count+1];
int weight=0;
for(int i=1;i<=count;i++){
int temp=sc.nextInt()/1024;
w[i]=temp;
weight+=temp;
}
int tmpResult=Knapsack2(weight/2,w);
System.out.println(max(weight-tmpResult,tmpResult)*1024);
}
private static int Knapsack2(int weight, int[] w){
int[][] c=new int[w.length][weight+1];
for(int i=1;i<w.length;i++){
for(int k=1;k<=weight;k++){
if(w[i]<=k){
c[i][k]=max(c[i-1][k],c[i-1][k-w[i]]+w[i]);
}else{
c[i][k]=c[i-1][k];
}
}
}
return c[w.length-1][weight];
}
private static int max(int a,int b){
return a>b?a:b;
}
}
转载请注明原文地址: https://ju.6miu.com/read-664867.html
