一种双核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 * 基本的0-1背包问题： * 已知有N类物品，每类物品都只有一件，对应的重量为w[i],价值为v[i]。 * 背包最多承重为W，在不超出承重范围的前提下，求能拿的物件的最大价值为多少 *这是DP的一个经典实例，可以用动态规划求解 *设dp(i,j)表示对于前i件物品，背包剩余容量为j时，能取得的最大价值 *状态转移方程：dp(i,j) = Max(dp(i-1,j), dp(i-1,j-w[i])+v[i]) *注： dp(i-1,j)—–>dp(i,j)，即不拿第i件物品 *dp(i-1,j-w[i])—–>dp(i,j)，即拿第i件物品 *当物品数量很多，背包的容量很大时,这时要用二维数组往往是不现实的 *我们可以进行空间压缩，使用一维数组实现 *状态转移方程： *dp(j)=Max(dp(j),dp(j-w[i])+v[i]) *注：当空间压缩后，对于背包的容量要采用倒序的方式！
public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int a[]=new int[n]; int sum=0;//所有任务需要的总时间 for(int i=0;i<n;i++){ a[i]=sc.nextInt()>>10; sum+=a[i]; } /* * 要求两个CPU尽可能各处理一半 * 即可让一个背包容量为总时间的一半，然后使背包尽量装满 */ sc.close(); //dp[j]为容量为j的背包实际装的重量 int dp[]=new int[sum/2+1]; for(int i=0;i<n;i++){ for(int j=sum/2;j>=a[i];j--){ //之所以从后往前，是因为此轮用到的是上一轮的数据，如果从前往后，就会把要用到的数据覆盖了 dp[j]=Math.max(dp[j],dp[j-a[i]]+a[i]); } } System.out.println(Math.max(dp[sum/2], sum-dp[sum/2])<<10); } }