动态规划解决01背包问题（java实现）

1. 01背包问题与背包问题的区别在于，01背包，物品的选择只有两种一种是拿，另一种是不拿，而背包问题在于，物品可以只取一部分。所以01背包问题不能用贪心算法解决。
2. 以dp[i][j]表示用i种物品，重量为j表示所取得的价值。
3. 对于第i种物品，如果第i种物品重量大于j，就证明第i种物品肯定不能取，这时的dp[i][j]=dp[i-1][j]
4. 如果第i种物品重量小于j，那就会出现两种情况，采用i的话，物品价值dp[i][j]=采用前面的i-1种物品，所占用的重量为j-i.getweight,所产生的价值+第i 种物品的价值，。如果不采用i，价值为dp[i-1][j]。换成数学表达式就是dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);
5. 比如当i=5,j=10时，dp[5][10]就代表了所取得的最大价值。到这里我们就完成了任务的一半，接下为我们要寻找到底哪些物品放入了背包，从前面的表达式我们可以发现，当dp[i][j]=dp[i-1][j-weight]时，这时为i的物品就会放入背包，所以我们从结果，开始往回走，遇到这种情况，就说明有物品放入背包，然后物品数减1，重量减去为i的重量，继续，最后就能求出哪 些物品放入背包了。
   6.参考代码如下：

package com.bc;

public class Test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
         int allweight=12;  //总价值 
         int num=8;   //物品
          bao[] baos=new bao[num+1];
          baos[1]=new bao(2, 13);
          baos[2]=new bao(1, 10);
          baos[3]=new bao(3, 24);
          baos[4]=new bao(2, 15);
          baos[5]=new bao(4, 28);
          baos[6]=new bao(5, 33);
          baos[7]=new bao(3, 20);
          baos[8]=new bao(1, 8);
          int[][] dp=new int[num+1][allweight+1];
          //构成动态规划表
          for(int i=0;i<=num;i++)
          {
              for(int j=0;j<=allweight;j++)
              {
                  if(i==0||j==0)
                  {
                      dp[i][j]=0;

                  }else {
                      if (j<baos[i].getWeight()) {
                        dp[i][j]=dp[i-1][j];
                    }else {
                        int value=baos[i].getValue();
                        int weight=baos[i].getWeight();
                        dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);
                    }
                }

                  System.out.println("dp"+"["+i+"]"+"["+j+"]"+dp[i][j]);
              }
          }


          int m=num;
          int n=allweight;
          int all=dp[m][n];
          //寻找哪些物品放入背包
           while(all>=0)
           {
               if (m>0&&dp[m][n]==dp[m-1][n]) {
                   m=m-1;

                }else {
                    System.out.println(baos[m]+"加入背包");
                    m=m-1;
                    if (m==0) {
                        return;
                    }else {
                        n=n-baos[m].getWeight();
                        all=all-baos[m].getWeight();
                    }

                }
           }
    }

}