背包01問題

背包01問題是一個經(jīng)典的算法。

問題是這樣描述的：一個背包最大容量為9kg，現(xiàn)在有5個物品，每個物品都有自己的重量，請問背包最后最多能裝多少重量的物品。5個物品的重量分別是2,2,4,8,6

解決這個問題可以用多種算法、貪心法、回溯法、動態(tài)規(guī)劃。

1. 貪心法：依次那物品，每次挑選最優(yōu)的情況，這樣認為最后就是得到的最優(yōu)解。這樣的解決思路可能會有問題，并不能保證每次都是正確的。對于這個問題是這樣解決：

   第一次取重量最小的 2， 這時背包重量為2沒有超過9再次挑選

   第二次取重量最小的2， 這時重量為4 沒有超過9再次挑選

   第三次取重量最小的4，這時重量為8沒有超過9再次挑選

   第四次取重量最小的6，這時重量為14超出重量所以最終結(jié)果為8

2. 回溯法：也是窮舉法，將所有可能的組合全部拼接出來，然后取符合條件的值。這樣的解決思路一定能得到最優(yōu)解，但是效率可能會比較低?；厮莘〞玫竭f歸，很難用語言描述清楚，在這里獻上代碼：

   // 回溯算法實現(xiàn)。注意：我把輸入的變量都定義成了成員變量。
   private int maxW = Integer.MIN_VALUE; // 結(jié)果放到 maxW 中
   private int[] weight = {2，2，4，6，3};  // 物品重量
   private int n = 5; // 物品個數(shù)
   private int w = 9; // 背包承受的最大重量
   public void f(int i, int cw) { // 調(diào)用 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 個物品
     }
   }
   
   

3. 動態(tài)規(guī)劃：傳說中的上帝視角，可以知道每次選擇的結(jié)果，并且知道下次選擇的結(jié)果。實際上他跟回溯法有些類似，但是不用遞歸實現(xiàn)。對于這個問題：每個物品都有兩種選擇放入包中，和不放入包中，這個決策會影響第二次放置物品，然后根據(jù)第一種情況推出第二種情況的所有所有取值，再推出第三種選擇，最終得到所有的情況。獻上代碼:

   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 物品個數(shù)
        * @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++) {
               //尋找上一層可能，如果是第一層則將放置該物品的下標設(shè)置為true
               //如果不是第一層，則將該層已經(jīng)設(shè)置為true的下標設(shè)為true 并把值取出與上一層的位置加和設(shè)置為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;
       }
   
       /**
        * 一維數(shù)組
        * @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{
                   //一定要從大到小計算，不然會出現(xiàn)重復計算的情況
                   /**
                    * 比如：第二個物品的重量為2
                    * 第一個物品不放第二個物品放則重量為2 所以將2位置設(shè)置為true
                    * 繼續(xù)循環(huán)重量，現(xiàn)在第二個位置的值是true，+2又將4位置的重量設(shè)置為true這樣是不符合道理的
                    * 倒序的話，依次往前走設(shè)置的值都在后面，遍歷是向前所以不會重復
                    */
                   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;
       }
   }