我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
具体例子：小明有个背包，最大装9kg物品，现在桌上有几个物品，重量（kg）分别是2,2,4,6,3 问，小明包里能装的最大多少kg？
private static int[] weight = {2,2,4,6,3}; // 物品重量
private static int n = 5; // 物品个数
private static int w = 9; // 背包承受的最大重量
代码如下：
weight:物品重量，n:物品个数，w:背包可承载重量 public int knapsack(int[] weight, int n, int w) { boolean[][] states = new boolean[n][w+1]; // 默认值false states[0][0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化 if (weight[0] <= w) { states[0][weight[0]] = true; } for (int i = 1; i < n; ++i) { // 动态规划状态转移
//--其实就是把states[i-1][j] 的数据，copy到下一个状态states[i],应为下一个状态要使用本次states做重量累加 for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包 if (states[i-1][j] == true) states[i][j] = states[i-1][j]; }
//这里做重量判断，没超过背包重量就塞进包里，j+weight[i]其实j代表的是背包当前的重量，+weight[i] for (int j = 0; j <= w-weight[i]; ++j) {//把第i个物品放入背包 if (states[i-1][j]==true) states[i][j+weight[i]] = true; } } for (int i = w; i >= 0; --i) { // 输出结果 if (states[n-1][i] == true) return i; } return 0; }
还可以使用一维数组解决该问题：
//使用一维数组 public static int knapsack2(int[] items, int n, int w) { boolean[] states = new boolean[w+1]; // 默认值false states[0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化 if (items[0] <= w) { states[items[0]] = true;//这里是哨兵，不写这个其实也可以 } for (int i = 1; i < n; ++i) { // 动态规划 for (int j = w-items[i]; j >= 0; --j) {//把第i个物品放入背包（这里倒着从w-items[i]判断，可以避免重复计算） System.out.println("i="+i+"\tj="+j+"\tstates[j]="+states[j]+"\titems[i]="+items[i]); if (states[j]==true) states[j+items[i]] = true; System.out.println(Arrays.toString(states)); } } for (int i = w; i >= 0; --i) { // 输出结果 count++; if (states[i] == true) return i; } return 0; }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。