背包01问题
背包01问题是一个经典的算法。
问题是这样描述的：一个背包最大容量为9kg，现在有5个物品，每个物品都有自己的重量，请问背包最后最多能装多少重量的物品。5个物品的重量分别是2,2,4,8,6
解决这个问题可以用多种算法、贪心法、回溯法、动态规划。
-
贪心法：依次那物品，每次挑选最优的情况，这样认为最后就是得到的最优解。这样的解决思路可能会有问题，并不能保证每次都是正确的。对于这个问题是这样解决：
第一次取重量最小的 2， 这时背包重量为2没有超过9再次挑选
第二次取重量最小的2， 这时重量为4 没有超过9再次挑选
第三次取重量最小的4，这时重量为8没有超过9再次挑选
第四次取重量最小的6，这时重量为14超出重量所以最终结果为8
-
回溯法：也是穷举法，将所有可能的组合全部拼接出来，然后取符合条件的值。这样的解决思路一定能得到最优解，但是效率可能会比较低。回溯法会用到递归，很难用语言描述清楚，在这里献上代码：
// 回溯算法实现。注意：我把输入的变量都定义成了成员变量。 private int maxW = Integer.MIN_VALUE; // 结果放到 maxW 中 private int[] weight = {2，2，4，6，3}; // 物品重量 private int n = 5; // 物品个数 private int w = 9; // 背包承受的最大重量 public void f(int i, int cw) { // 调用 f(0, 0) if (cw == w || i == n) { // cw==w 表示装满了，i==n 表示物品都考察完了 if (cw > maxW) maxW = cw; return; } f(i+1, cw); // 选择不装第 i 个物品 if (cw + weight[i] <= w) { f(i+1,cw + weight[i]); // 选择装第 i 个物品 } }
-
动态规划：传说中的上帝视角，可以知道每次选择的结果，并且知道下次选择的结果。实际上他跟回溯法有些类似，但是不用递归实现。对于这个问题：每个物品都有两种选择放入包中，和不放入包中，这个决策会影响第二次放置物品，然后根据第一种情况推出第二种情况的所有所有取值，再推出第三种选择，最终得到所有的情况。献上代码:
public class OneAndTwoPackage { public static int WEIGHT_MAX = 20;//最大重量 public static void main(String[] args) { int[] weightList = {7,2,3,6,1}; //每个物品的重量 System.out.println(dynamicPlanOne(weightList, 5)); System.out.println(dynamicPlanTwo(weightList, 5)); } /** * * @param weightList 物品重量 * @param num 物品个数 * @return */ public static int dynamicPlanOne(int[] weightList, int num){ //解决这个问题的思路就是 /** * 每个物品都有两种选择，后一种基于前一种的可能会有更多的选择，将所有的可能列举并记录总重量 * 第一个 有两种可能 放 总重量为2 不放为0 * 第二个 有三种可能 放 2,4 不放0,2 总共为0,2,4 * 第三个 有5种可能 放 4,6,8 不放 0,2,4 */ boolean[][] weightFlag = new boolean[num][WEIGHT_MAX+1];//初始化所有的标记默认为false weightFlag[0][0] = true; for (int i = 0; i < num; i++) { //寻找上一层可能，如果是第一层则将放置该物品的下标设置为true //如果不是第一层，则将该层已经设置为true的下标设为true 并把值取出与上一层的位置加和设置为true if (0 <= i-1){ boolean[] preWeight = weightFlag[i-1]; for (int i1 = 0; i1 <= WEIGHT_MAX; i1++) { if (preWeight[i1]){ //不放 weightFlag[i][i1] = true; //放 int weight = weightList[i] + i1; if (weight <= WEIGHT_MAX) weightFlag[i][weight] = true; } } }else { weightFlag[i][weightList[i]] = true; } } //最后一层，的最大值即为最大重量 for (int j = WEIGHT_MAX; j >=0 ; j--) { if (weightFlag[num-1][j]){ return j; } } return 0; } /** * 一维数组 * @param weightList * @param num * @return */ public static int dynamicPlanTwo(int[] weightList, int num){ boolean[] weightFlg = new boolean[WEIGHT_MAX+1];//所有重量的分层 weightFlg[0] = true;//不放的时候为0 for (int i = 0; i < num; i++) { if (i-1 < 0){ //第一层放与不放 weightFlg[weightList[i]] = true; }else{ //一定要从大到小计算，不然会出现重复计算的情况 /** * 比如：第二个物品的重量为2 * 第一个物品不放第二个物品放则重量为2 所以将2位置设置为true * 继续循环重量，现在第二个位置的值是true，+2又将4位置的重量设置为true这样是不符合道理的 * 倒序的话，依次往前走设置的值都在后面，遍历是向前所以不会重复 */ for (int weightMax = WEIGHT_MAX; weightMax > 0; weightMax--) { if (weightFlg[weightMax]){ if (weightMax+weightList[i] <= WEIGHT_MAX){ weightFlg[weightMax+weightList[i]] = true; } } } } } for (int i = weightFlg.length - 1; i >= 0; i--) { if (weightFlg[i]){ return i; } } return 0; } }
