/** * 0-1背包问题 * @param w w[index] 当前货物的总重量 * @param v v[index] 当前货物的总价值 * @param index 当前的货物号 * @param alreadyW 0--index 已做出决定,所形成的目前重量 * @param bag 可装的总重量 * @return 返回最大价值 */ public static int process(int[] w,int[] v,int index,int alreadyW,int bag){ //base case 背高超重了,不能再放物品了 if(alreadyW>bag){ return -1; } //没有物品了 if(index==w.length){ return 0; } //当前物品不放所获得的最大价值 int p1=process(w,v,index+1,alreadyW,bag); //当前物品放入背包所获得的最大价值 int p2=process(w,v,index+1,alreadyW+w[index],bag); int pNext=-1; if(p2!=-1){ pNext=v[index]+p2; } return Math.max(p1,pNext); }
/** * 0-1背包问题 * @param w 当前货物的总重量 * @param v 当前货物的总价值 * @param index 当前的货物号 * @param rest 剩余可装入的重量 * @return 返回最大价值 */ public static int process(int[] w,int[] v,int index,int rest) { //没有容量了 if (rest == 0) { return 0; } //没有物品了 if (index == w.length) { return 0; } int p1 = process(w, v, index + 1, rest); int p2 = 0; //放入当前物品的话,要判段容量是否够 if (rest >= w[index]) { p2 = v[index] + process(w, v, index + 1, rest - w[index]); } return Math.max(p1, p2); }