【背包问题】是【动态规划】中十分经典的一类问题，背包问题本质熵属于组合优化的【NP完全问题】，简单理解就是无法直接求解的问题。只能通过【穷举】和【验证】进行求解。

抽象模型

【背包问题】泛指一类【给定价值与成本】，同时【限定决策规则】，在这样的条件下，如何实现价值最大化的问题。

0-1背包

给定物品价值和体积（或重量），在规定容量下，如何使得所选物品的价值最大化。
【题目】有N个物品，一个容量为C的背包，每件物品只有1件，第i件物品的价值为v[i]，体积为w[i]，求解将哪些物品装入背包，可使得这些物品的总体积不超过背包容量，且总价值最大。

  1. import java.util.Scanner;
  3. /**
  4. 3 4
  5. 4 2 3
  6. 4 2 3
  8. 3 5
  9. 4 2 3
  10. 4 2 3
  11.  */
  12. class Main {
  14.     public static void main(String[] args) {
  15.         Scanner scanner = new Scanner(System.in);
  16.         int N = scanner.nextInt();
  17.         int C = scanner.nextInt();
  18.         int[] value = new int[N];
  19.         int[] weight = new int[N];
  20.         for (int i = 0; i < N; i++) value[i] = scanner.nextInt();
  21.         for (int i = 0; i < N; i++) weight[i] = scanner.nextInt();
  22.         System.out.println(maxValue(N, C, value, weight));
  23.     }
  24.     //朴素方式
  25.     public static int maxValue(int N, int C, int[] value, int[] weight) {
  26.         int[][] dp = new int[N][C+1]; //前i件物品，在容量j的限制下，获取得到的最大价值
  28.         //base case，第1件物品
  29.         for (int j = 0; j <= C; j++) {
  30.             dp[0][j] =j-weight[0] >= 0 ? value[0] : 0;
  31.         }
  32.         //处理剩余物品
  33.         for (int i = 1; i < N; i++) {
  34.             for (int j=0; j<=C; j++) {
  35.                 int noSelect = dp[i-1][j];
  36.                 int doSelect = j>=weight[i] ? dp[i-1][j-weight[i]] + value[i] : 0;
  37.                 dp[i][j] = Math.max(noSelect, doSelect);
  38.             }
  39.         }
  40.         return dp[N-1][C];
  41.     }
  42. }
//一维优化
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int C = scanner.nextInt();
        int[] value = new int[N];
        int[] weight = new int[N];
        for (int i = 0; i < N; i++) value[i] = scanner.nextInt();
        for (int i = 0; i < N; i++) weight[i] = scanner.nextInt();
        System.out.println(maxValue(N, C, value, weight));
    }
    //一维优化
    public static int maxValue(int N, int C, int[] value, int[] weight) {
        int[] dp = new int[C+1];
        //处理剩余物品
        for (int i = 0; i < N; i++) {
            for (int j=C; j>=weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-weight[i]]+value[i]);
            }
        }
        return dp[C];
    }
}

将原问题抽象成0-1背包

【题目】LeetCode上的416，分割等和子集，难度Medium。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成2个子集，使得两个子集的元素和相等。注意，每个数组的元素不会超过100，数组大小不会超过200。
【分析】抽象成能否从数组挑选若干元素，使得元素总和等于所有元素的一半。0-1背包模型：容量为target，物品为原数组（价值和体积一样），每个物品只能挑选一件。

//朴素实现方式
class Solution {
    public boolean canPartition(int[] nums) {
        //抽象成背包问题，容量为sum/2，价值和体积都是nums值，最终结果为dp[n-1][sum/2]
        int sum = 0;
        int n = nums.length;
        for (int i=0; i<n; i++) {
            sum += nums[i];
        }
        int half = sum / 2;

        if (half * 2 != sum) {
             return false; //无法凑整
        }
        //0-1背包的朴素实现
        //base case
        int[][] dp = new int[n][half+1];
        for (int j=0; j<=half; j++) {
            dp[0][j] = j>=nums[0] ? nums[0] : 0;
        }
        //处理剩余的
        for (int i=1; i<n; i++) {
            for (int j=0; j<=half; j++) {    
                int noSelect = dp[i-1][j];
                int doSelect = j>=nums[i] ? dp[i-1][j-nums[i]]+ nums[i] : 0;
                dp[i][j] = Math.max(noSelect, doSelect);
            }
        }
        // for (int i=0; i<n; i++) {
        //     for (int j=0; j<=half; j++) {
        //         System.out.print(dp[i][j] + " ");
        //     }
        //     System.out.println();
        // }
        return dp[n-1][half] == half;

    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        //抽象成背包问题，容量为sum/2，价值和体积都是nums值，最终结果为dp[n-1][sum/2]
        int sum = 0;
        int n = nums.length;
        for (int i=0; i<n; i++) {
            sum += nums[i];
        }
        int half = sum / 2;

        if (half * 2 != sum) {
             return false; //无法凑整
        }
        //0-1背包的一维优化
        int[] dp = new int[half+1];
        for (int i=0; i<n; i++) {
            for (int j=half; j>=nums[i]; j--) {    
                dp[j] = Math.max(dp[j], dp[j-nums[i]]+ nums[i]);
            }
        }
        return dp[half] == half;

    }
}

//修改背包的状态定义，直接求解
//dp[i][j]考虑前i个数值，其选择数字总和刚好为j