0-1 背包问题

0-1 背包问题

对于一个容量为W的背包和N个物品，每个物品对应有一个价值val和重量weight，如何使背包中的物品价值最大？现在有N个物品，那么对于第i个物品，有价值val[i]，重量weight[i]。

假设现在背包重量为4，物品有3个，价值val = {2,1,3},对应的重量weight = {4,2,3},那么结果应为6.

初始化一个dp[N][W]数组,其中dp[i][w]表示对于前i个物品，当 背包容量为w时，最多可以装下的价值为dp[n] [w]

①对于dp[0] [...],此时可以理解为对于前0个物品的最大价值，肯定为0

②对于dp[..] [0],此时可以理解为当前背包容量为0，那么dp[...] [w]也为0.

**

   * @param W      : 背包总容量
      @param N      :  物品个数
        * @param val    每个物品对应的n
           @param weight 每个物品的重量
             * @return
               /
public int packAge(int W, int N, int[] val, int[] weight) {    
	//这里n和数组长度是相等的，所以这个参数可以不要
    int[][] dp = new int[N][W];

    Arrays.fill(dp, 0);  //初始化全为0

    for (int n = 1; n < N; n++) {
        for (int w = 1; w < W; w++) {
            dp[n][w] = Math.max(
                  //1.当前物品n放进背包
                 //2.当前物品n不放进背包
            );
        }
    }

    return dp[n - 1][w - 1];
}

如果当前物品i不放进背包，那么dp[n] [w] 肯定就等于dp[n-1] [w]

如果当前物品i放进背包，那么

dp[n][w] = Math.max(dp [n-1] [W-weight[n]] + val[n],dp[n-1] [w]);
//如果要放进去，那么就取放进去当前物品之后跟不放时的最大值
//dp[n-1][w-weigt[n]],代表没有放进当前物品时的最大价值（n-1：代表未放当前物品 [w-weight[n]]: 因为总容量是W,所以要减去当前未放置的n的容量）

因此：

public int packAge(int W, int N, int[] val, int[] weight) {

        //这里n和数组长度是相等的，所以这个参数可以不要
        int[][] dp = new int[N + 1][W + 1];

        for (int n = 1; n <= N; n++) {
            for (int w = 1; w <= W; w++) {
                //这种情况下只能选择不放
                if (w - weight[n - 1] < 0) {
                    dp[n][w] = dp[n - 1][w];
                } else {
                    dp[n][w] = Math.max(dp[n - 1][w - weight[n - 1]] + val[n - 1], dp[n - 1][w]);
                }
            }
        }

        return dp[N][W];
    }