给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
博主个人认为，从左往右的尝试模型这一类题型的关键点在于讨论当前位置的东西要或者不要，然后再具体分析，详情看代码吧，都写了很详细的注释。
补充一点：方法二是这一类题最常见的暴力解法，跟方法一相比恰好是逆向思维。
package com.harrison.class12; public class Code06_Knapsack { // 不变参数 w[] v[] bag // alreadyW 0~index位置的货物已经做过决定了，现在形成的重量 // 返回index及其往后位置货物的最大价值 // 返回 -1 认为方案无效， // 返回不是-1，返回值就是真实的价值 public static int process1(int[] w,int[] v,int index,int alreadyW,int bag) { if(alreadyW>bag) {// 超过了载重，方案无效 return -1; } // 重量没吵 && 没有货物了，所以此时的最大价值就是0 if(index==w.length) { return 0; } // 没有要当前货物 int p1=process1(w, v, index+1, alreadyW, bag); // 要了当前的货物 int p2next=process1(w, v, index+1, alreadyW+w[index], bag); int p2=-1; // 如果要了当前位置的货物 && 重量没有超过bag // 那么这种情况下的最大价值就要加上当前这个货物的价值 if(p2next!=-1) { p2=p2next+v[index]; } // 返回要当前货物和不要当前货物两种情况下的最大价值 return Math.max(p1, p2); } public static int maxValue1(int[] w,int[] v,int bag) { if(w==null || v==null || w.length!=v.length || w.length==0) { return 0; } return process1(w, v, 0, 0, bag); } // rest 当前剩余的重量，其余参数跟你上面方法一样 public static int process2(int[] w,int[] v,int index,int rest) { // 如果没有剩余重量了，方案无效 if(rest<0) { return -1; } // 如果有剩余空间但是没有货物了 // 那么index及其往后位置的货物的最大价值就是0 if(index==w.length) { return 0; } // 不要当前位置的货物，所以rest没变 int p1=process2(w, v, index+1, rest); // 要了当前位置的货物，所以剩余空间要减去当前货物的重量 int p2next=process2(w, v, index+1, rest-w[index]); int p2=-1;// 要当前位置货物的话，可能会导致方案无效，也就是剩余重量可能会<0 // 如果要了当前货物 && 还有剩余重量（方案有效） if(p2next!=-1) { p2=p2next+v[index]; } // 返回要跟不要当前货物两种情况下的最大值 return Math.max(p1, p2); } public static int maxValue2(int[] w,int[] v,int bag) { if(w==null || v==null || w.length!=v.length || w.length==0) { return 0; } return process2(w, v, 0, bag); } public static void main(String[] args) { int[] w = { 3, 2, 4, 7, 3, 1, 7 }; int[] v = { 5, 6, 3, 19, 12, 4, 2 }; int bag=15; System.out.println(maxValue1(w, v, bag)); System.out.println(maxValue2(w, v, bag)); } }
