LeetCode BackPack 背包问题

谁借莪１个温暖的怀抱￠ 2022-06-07 01:39 127阅读 0赞

//从上个月末之后就开始有点浮躁起来，本来计划国庆查漏补缺的，结果网卡光荣的坏了ORZ……无论如何，OFFER现在还没有拿到，即便是拿到了也不该放松学习的状态。Stay Hungry，Stay Foolish

背包问题是动态规划的经典问题，LeetCode上有五种背包的变种问题，现在总结一下。

## 背包问题一（最大放入重量） ##

题目描述：

Given n items with size Ai, an integer m denotes the size of a backpack.
    How full you can fill this backpack?

样例输入：

[2,3,5,7],11
    [2,3,5,7],12

样例输出：

10
    12

最普通的一种背包问题，求在指定容量为m的背包中可以放入的最大容量

首先介绍一种使用二维辅助数组`dp[i][j]`的方法

二维数组`dp[i][j](0<=i<A.length,0<=j<=m)`表示在最大容量为j，可放入容量是A\[0..i\]的情况下可放入的最大容量，可以分为两种情况

*  当前背包最大容量小于物品的重量，可容纳的最大重量是`dp[i-1][j]`
 *  当前背包最大容量小于物品重量，可容纳的最大重量是`max(dp[i-1][j],dp[i-1][j-A[i]+A[i])`

![这里写图片描述][SouthEast]

代码如下

public int backPack(int[] A, int m) {
        int[][] dp = new int[A.length][m + 1];
        for (int j = 1; j < m + 1; j++) {
            if (j == A[0]) {
                dp[0][j] = A[0];
            } else {
                dp[0][j] = 0;
            }
            for (int i = 1; i < A.length; i++) {
                if (j < A[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - A[i]] + A[i], dp[i - 1][j]);
                }
            }
        }
        return dp[A.length - 1][m];
    }

实际上也可以优化成一维数组

![这里写图片描述][SouthEast 1]

代码如下

public int backPack(int[] A, int m) {
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j - A[i]] + A[i], dp[j - 1]);
                }
            }
        }
        return dp[m];
    }

## 背包问题二（最大放入价值） ##

题目描述：

Given n items with size Ai and value Vi, and a backpack with size m.
     What's the maximum value can you put into the backpack?

样例输入

10,[2,3,5,7],[1,5,2,4]

样例输出

在第一类背包问题的基础上，每个物品增加了价值，求可放入背包的物品的最大价值

跟第一类问题类似，不同就是数组存放的是最大价值

首先第一种二维数组的方法

![这里写图片描述][SouthEast 2]

public int backPack(int[] A, int[] V, int m) {
        int[][] dp = new int[A.length][m + 1];
        for (int j = 1; j < m + 1; j++) {
            if (j == A[0]) {
                dp[0][j] = V[0];
            } else {
                dp[0][j] = 0;
            }
            for (int i = 1; i < A.length; i++) {
                if (j < A[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - A[i]] + V[i], dp[i - 1][j]);
                }
            }
        }
        return dp[A.length - 1][m];
    }

第二种

public int backPack(int[] A, int[] V, int m) {
          int[] dp = new int[m + 1];
          for (int i = 0; i < A.length; i++) {
              for (int j = m; j > 0; j--) {
                  if (j >= A[i]) {
                      dp[j] = Math.max(dp[j - A[i]] + V[i], dp[j - 1]);
                  }
              }
          }
          return dp[m];
      }

## 背包问题三（最大价值+可重复选择） ##

题目描述

Given n kind of items with size Ai and value Vi( each item has an infinite number available)
     and a backpack with size m.
     What's the maximum value can you put into the backpack?

样例输入

10,[2,3,5,7],[1,5,2,4]

样例输出

在第二类的基础上，每个物品可以选择多次

public int backPackIII(int m, int[] A, int[] V) {
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
                }
            }
        }
        return dp[m];
    }

## 背包问题四（最大重量+所有可能结果） ##

题目描述：

Given an integer array nums with all positive numbers and no duplicates,
     find the number of possible combinations that add up to a positive integer target.

样例输入

[1,2,4],4

样例输出

在第一类的基础上，增加了求所有可放入的可能数

public int backPackVI(int[] nums, int target) {
       int[] dp = new int[target + 1];
       dp[0] = 1;
       for (int j = 1; j <= target; j++) {
           for (int i = 0; i < nums.length; i++) {
               if (j >= nums[i]) {
                   dp[j] += dp[j - nums[i]];
               }
           }
       }
       return dp[target];
    }

## 背包问题五（最大重量+所有可能结果+不同排列） ##

题目描述：

Given n items with size nums[i] which an integer array and all positive numbers.
     An integer target denotes the size of a backpack. Find the number of possible fill the backpack.
     Each item may only be used once

样例输入：

[1,2,3,3,7],7

样例输出：

在上一种情况下，不同的排序也算一种

public int backPackVI(int[] nums, int target) {
    int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }

[SouthEast]: /images/20220607/5885c51bd9c041b5b2d59bca8876e71f.png
[SouthEast 1]: /images/20220607/823c9cfa0b9d4996a89f0cbf8103dacb.png
[SouthEast 2]: /images/20220607/ef67d0d136504f96a6af8466c984de6f.png