背包问题

一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述:

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

输出描述:

输出一个整数，表示最少需要处理的时间

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);
        }
    }
}

解析：

核心代码就是以上16,17,18三行，实际就用了01背包空间优化的策略。 思路：根据题目意思，两个CPU平摊任务，然后输出执行这些任务的最小时间，最理想的情况是，每个CPU执行的任务占所有任务的总时间的一半（wholeTime/2），这样两个CPU执行的时间差就是最小的，输出的结果就是最小的，但任务只能由一个CPU独立完成，所以单个任务的执行时间已经是不可分割的了。解决的办法就是尽量让单个CPU执行的任务总时间接近wholeTime/2，越接近这个值，则这个CPU和另一个CPU的执行时间差就必定越小。也就能得到最优解，所以只要讨论一个CPU即可，而且希望它的执行时间越接近wholeTime/2就越好，这就与01背包问题挂上钩了，问题转化为限制背包的容量为wholeTime/2，每个任务转化为每个物品，物品的价值和大小都是任务的执行时间，这样一来，只要求得背包总价值最大即可得到原问题的答案了。

完成任务有个总时间，2个cpu 执行 最快的 就是 一个人执行 一半，
// dp[j]表示在容量为j的情况下可存放的重量
// 如果不放arr[i]重量为dp[j],如果放arr[i]重量为dp[j-arr[i]]+arr[i];
任务的value : 1 3 3 3 7 ; 任务数量为 1 1 1 1 ;单个cpu 最多完成为： sum/2=8;单个CPU 分别循环 1 ，2,3,4 个任务； 以4 为例 最大可执行 4个任务；dp[8], 如果把4 任务放入则 ，d[j]=arr[4]+ 剩下的能放置的质量;d[8]=arr[4]+d[8-arr[4]] 第四个任务的value ;// 循环后会得到最大值 ；

假定

背包的最大容量为W，N件物品，每件物品都有自己的价值和重量，将物品放入背包中使得背包内物品的总价值最大。

Paste_Image.png

  1. public class sf {  
  2.   
  3.     public static void main(String[] args) {  
  4.         // TODO Auto-generated method stub  
  5.         int[] weight = {3,5,2,6,4}; //物品重量  
  6.         int[] val = {4,4,3,5,3}; //物品价值  
  7.         int m = 12; //背包容量  
  8.         int n = val.length; //物品个数  
  9.           
  10.         int[] f = new int[m+1];  
  11.         for(int i=0;i<f.length;i++){     //不必装满则初始化为0  
  12.             f[i] = 0;  
  13.         }  
  14.         for(int i=0;i<n;i++){  
  15.             for(int j=f.length-1;j>=weight[i];j--){  
  16.                 f[j] = Math.max(f[j], f[j-weight[i]]+val[i]);  
  17.             }  
  18.         }  
  19.         for(int i=0;i<f.length;i++){  
  20.             System.out.print(f[i]+" ");  
  21.         }  
  22.         System.out.println();  
  23.         System.out.println("最大价值为"+f[f.length-1]);  
  24.     }  
  25. }