美文网首页
背包01问题

背包01问题

作者: caopengflying | 来源:发表于2019-03-29 17:53 被阅读0次

    背包01问题


    背包01问题是一个经典的算法。

    问题是这样描述的:一个背包最大容量为9kg,现在有5个物品,每个物品都有自己的重量,请问背包最后最多能装多少重量的物品。5个物品的重量分别是2,2,4,8,6

    解决这个问题可以用多种算法、贪心法、回溯法、动态规划。

    1. 贪心法:依次那物品,每次挑选最优的情况,这样认为最后就是得到的最优解。这样的解决思路可能会有问题,并不能保证每次都是正确的。对于这个问题是这样解决:

      第一次取重量最小的 2, 这时背包重量为2没有超过9再次挑选

      第二次取重量最小的2, 这时重量为4 没有超过9再次挑选

      第三次取重量最小的4,这时重量为8没有超过9再次挑选

      第四次取重量最小的6,这时重量为14超出重量所以最终结果为8

    2. 回溯法:也是穷举法,将所有可能的组合全部拼接出来,然后取符合条件的值。这样的解决思路一定能得到最优解,但是效率可能会比较低。回溯法会用到递归,很难用语言描述清楚,在这里献上代码:

      // 回溯算法实现。注意:我把输入的变量都定义成了成员变量。
      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 个物品
        }
      }
      
      
    1. 动态规划:传说中的上帝视角,可以知道每次选择的结果,并且知道下次选择的结果。实际上他跟回溯法有些类似,但是不用递归实现。对于这个问题:每个物品都有两种选择放入包中,和不放入包中,这个决策会影响第二次放置物品,然后根据第一种情况推出第二种情况的所有所有取值,再推出第三种选择,最终得到所有的情况。献上代码:

      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;
          }
      }
      

    相关文章

      网友评论

          本文标题:背包01问题

          本文链接:https://www.haomeiwen.com/subject/bejrbqtx.html