01背包问题

两种思路：
1. 求取完 n 个物品后，使箱子的剩余空间为最小
2. 求取完 n 个物品所占用空间的最大值，结果就是用总体积-所占空间总和的最大值即可

以第一种方式进行说明：
解法一：二维数组+动态规划
容量为 V -> 背包总容量 V
v[i] -> n 个物品的各自体积
dp[i][j] -> 在i个物品中选取完成后，在不超过j容量的前提下，剩余的最小容量
状态转移方程：
选i：dp[i][j] = dp[i-1][j-v[i]]
不选i：dp[i][j] = dp[i-1][j]
即：dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-v[i]])

注意：因为在i=0时，即一件商品都没选择的时候，剩余的背包容量为当前容量，所以需要先遍历初始化dp[0][j]的背包容量，表示在不选择任何一个物品时，剩余容量的最小值就是当前背包容量

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int totalV = scan.nextInt();
        int n = scan.nextInt();
        int[] a = new int[n+10];
        for(int i=1; i<=n; i++){
            a[i] = scan.nextInt();
        }
        int[][] dp = new int[n+10][totalV+10];
        for(int i=0; i<=totalV; i++){//初始化dp[0][j],表示在不选择任何一个物品时，剩余容量的最小值就是当前背包容量
            dp[0][i] = i;
        }

        for(int i=1; i<=n; i++){
            for(int j=0; j<=totalV; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= a[i]){
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j-a[i]]);
                }
            }
        }

        System.out.println(dp[n][totalV]);

    }
}

解法二：一维数组+动态规划
因为在解法一中，状态转移方程只使用到了i-1和j-a[i]，所以对于二维数组来说，其他记录的状态都是多余的，所以我们可以使用滚动数组来对解法一进行优化
状态转移方程：dp[j] = dp[j-a[i]]

注意：当变为dp[j] = dp[j-a[i]]后，对应的二维状态转移方程为：dp[i][j] = dp[i][j-a[i]]和原二维转移方程矛盾，因为在顺序遍历过程中会导致i-1层的数据先被覆盖，所以需要逆序遍历，这样就会先计算高层元素而不会影响底层元素

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int totalV = scan.nextInt();
        int n = scan.nextInt();
        int[] a = new int[n+10];
        for(int i=1; i<=n; i++){
            a[i] = scan.nextInt();
        }
        int[] dp = new int[totalV+10];
        for(int i=0; i<=totalV; i++){
            dp[i] = i;
        }

        for(int i=1; i<=n; i++){
            for(int j=totalV; j>=a[i]; j--){
                dp[j] = Math.min(dp[j], dp[j-a[i]]);
            }
        }

        System.out.println(dp[totalV]);

    }
}