背包问题
一种双核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. }
