算法笔记 -- 背包问题

背包问题是一种比较经典的动态规划问题,在这里把几种背包都讨论一下。

0-1背包

给你一个可装载重量为 c 的背包和 n 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 w[i]，价值为 v[i]，现在让你用这个背包装物品，最多能装的价值是多少？

如果使用动态规划分析，首先看有什么状态，对于每件物品，有选和不选两个状态。

定义$dp[i][j]$为对于前$i$个物品，当前背包容量为$j$时的最大价值，很明显要返回$dp[n][c]$。

若不选第$i$件物品来说，$dp[i][j]=dp[i-1][j]$，等价于只考虑前$i-1$件物品，容量为$j$时的最大值；

若选第$i$件物品，$dp[i][j]=dp[i-1][j-w[i]]+v[i]$，考虑前面$i-1$件物品，容量因为选了当前的物品，所以剩余容量就为$j-v[i]$。

还有一个额外的条件为，若要选则当前的第$i$件物品，背包的剩余容量$j$应该要$\ge w[i]$。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int c = in.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        for(int i = 0; i < n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        System.out.println(zeroOneBackpack(n,c,v,w));
        in.close();
    }
    public static int zeroOneBackpack(int n, int c, int[] v, int[] w) {
        int[][] dp = new int[n + 1][c + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= c; j++) {
                if(j < w[i - 1]) {
                    // 此时背包容量不足，只能选择不装
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                }
            }
        }
        return dp[n][c];
    }
}

完全背包

有一个背包，最大容量为 c，有一系列物品 ，每个物品的重量为 weight[i]，每个物品的数量无限。请问背包的最大价值是？

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int c = in.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        for(int i = 0; i < n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        System.out.println(completeBackpack(n,c,v,w));
        in.close();
    }
    public static int completeBackpack(int n, int c, int[] v, int[] w) {
        int[][] dp = new int[n + 1][c + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= c; j++) {
                if(j < w[i - 1]) {
                    // 此时背包容量不足，只能选择不装
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w[i - 1]] + v[i - 1]);
                }
            }
        }
        return dp[n][c];
    }
}

---

完全背包问题还有以下变种，即求给定的物品组成容量为c的背包的方案数。

有一个背包，最大容量为 c，有一系列物品 ，每个物品的重量为 weight[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

状态有两个，就是「背包的容量」和「可选择的物品」，选择还是「装进背包」或者「不装进背包」。

定义$dp[i][j]$为只使用前$i$个物品，当背包容量为$j$时的方法总数。

显然$dp[0][...]=0$，因为不使用物品，也就不存在方法，$dp[...][0]=1$，因为背包容量为0时，只有什么都不选这一种方法，最后要求得的就是$dp[weight.length][c]$。

import java.util.*;
public class Main {
    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
        int c = in.nextInt();
        int n = in.nextInt();
        int[] weight = new int[n];
        for(int i = 0; i < n; i++) {
            weight[i] = in.nextInt();
        }
        System.out.println(completeBackpackScheme(c, weight));
        in.close();
    }
	public static int completeBackpackScheme(int c, int[] weight) {
        int n = weight.length;
        int[][] dp = int[n + 1][c + 1];
        for (int i = 0; i <= n; i++) 
            dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c; j++)
                if (j - weight[i - 1] >= 0)
                    dp[i][j] = dp[i - 1][j] 
                             + dp[i][j - weight[i - 1]];
                else 
                    dp[i][j] = dp[i - 1][j];
        }
        return dp[n][c];
	}
}

完全背包的关键点就在于如果选择了第$i$件物品，还是可以继续选择第$i$件物品，所以$dp[i][j]=Math.max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]);$