MIN =
Integer.MIN_VALUE; 3 4 @org.junit.Test 5publicvoid test() { 6int[] w = {3, 2, 2
}; 7int[] v = {5, 10, 20
}; 8knapsackOptimal(5
, w, v); 9 } 1011/**12 * 01背包-容量压缩 13 * 14 * @param c 包容量 15 * @param weight 各物品质量 16 * @param value 各物品价值 17*/18publicvoidknapsackOptimal(
intc,
int[] weight,
int[] value) { 19intn = weight.length;
//物品数量20int[] w =
newint[n + 1
]; 21int[] v =
newint[n + 1
]; 22int[][] G =
newint[n + 1][c + 1
]; 23for(
inti = 1; i < n + 1; i++
) { 24w[i] = weight[i - 1
]; 25v[i] = value[i - 1
]; 26 } 2728//初始化values[0...c]=0————在不超过背包容量的情况下,最多能获得多少价值 29//原因:如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了30int[] values =
newint[c + 1
]; 31//初始化values[0]=0,其它全为负无穷————解决在恰好装满背包的情况下,最多能获得多少价值的问题 32//原因:只有容量为0的背包可以什么物品都不装就能装满,此时价值为0,其它容量背包均无合法的解,属于未定义的状态,应该被赋值为负无穷33/*for (int i = 1; i < values.length; i++) { 34 values[i] = MIN; 35 }*/3637for(
inti = 1; i < n + 1; i++
) { 38for(
intt = c; t >= w[i]; t--
) { 39if(values[t] < values[t - w[i]] +
v[i]) { 40values[t] = values[t - w[i]] +
v[i]; 41G[i][t] = 1
; 42 } 43 } 44 } 45System.out.println("最大价值为: " +
values[c]); 46System.out.print("装入背包的物品编号为: "
); 47/*48 输出顺序:逆序输出物品编号 49 注意:这里另外开辟数组G[i][v],标记上一个状态的位置 50 G[i][v] = 1:表示物品i放入背包了,上一状态为G[i - 1][v - w[i]] 51 G[i][v] = 0:表示物品i没有放入背包,上一状态为G[i - 1][v] 52*/53inti =
n; 54intj =
c; 55while(i > 0
) { 56if(G[i][j] == 1
) { 57System.out.print(i + " "
); 58j -=
w[i]; 59 } 60i--
; 61 } 62 } 63}
来源: http://www.bubuko.com/infodetail-2013613.html