背包问题详解

背包问题核心思想为DP(Dynamic Programming),本文基于核心思路实现逐步推导.

最大价值简称:mv

01背包

例题描述:

有 N 件物品和一个容量为 M 的背包。第 i 件物品的重量是 Wi​，价值是 Di​。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入:

第一行：物品个数 N 和背包大小 M。

第二行至第 N+1 行：第 i 个物品的重量 Wi​ 和价值 Di​。

实验数据:

4 6 1 4 2 6 3 12 2 7

预测结果

23

题目地址

P2871

基础假设:dp[i][j] 表示在第i 个元素并且剩余容量为j时的最大价值

满足最优子结构和无后效性

基于基础假设,尝试得出2维dp表

采用递推实现

注:

1. 设置dp[i] 设置i=0 目的是防止dp[i-1] 越界
2. 表中数据表示此时的mv

代码:

    @Test
    void contextLoads() {
        int n = 4;
        int m = 6;
        int[] w = {0,1,2,3,2};
        int[] v = {0,4,6,12,7};

        int [][] dp = new int[5][7];

        for (int i = 1; i < 5; i++) {
            for (int j = 0; j < 7 ; j++) {
                if(j < w[i]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
                }
            }
        }

        for (int i = 0; i < 5; i++) {
            for (int i1 = 0; i1 < 7; i1++) {
                System.out.print(dp[i][i1]);
            }
            System.out.println();
        }
    }

解释表格得出过程:

j=0或i=0时,表示容量为0,此时mv显然为0

i=1且j=1时,容量j 等于w ,不拿mv=0,拿取mv=4,选择拿取

i =1且j>1时,mv=4恒成立

i=2且j=1时,j<w,无法拿取,mv = 4

i=2且j=2时,j=w,满足拿取条件:不拿,mv = 4,拿取,mv = dp[1][2-2]+v[2]=0+6=6,故mv=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) =6

i=2且j=3时,j>=w,满足拿取条件:不拿,mv=4,拿取mv =dp[1][3-2]+v[2]=4+6 =10,故mv = 10

之后情况依次递推

注:当i=1时,比较依然存在只是无意义

由过程推导得出:打表时的核心方程:当j > w[i],dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

当j<w[i],dp[i][j]=dp[i-1][j];

核心流程解释完毕

优化:

显然建表时,表大小约为(n+1)(m+1),可能造成MLE

理论优化思路:

i=n行的数据仅和i=n-1有关,考虑压缩数组(或者滚动数组),此时数组变为一维,核心方程变为j>=w[i],dp[j]=max(dp[j],dp[j-w[i]]+v[i]),j<w,dp[j]=dp[j],显然可以合并为 j=w[i],dp[j]=max(dp[j],dp[j-w[i]]+v[i])

代码优化思路:

直接将j>=w[i]提升至循环体内,减少比较次数

注意点:

对于j的遍历优化后需要从后往前,因为比较时需要dpj-w[i],从前向后会导致数据覆盖 优化后的测试代码:

@Test void contextLoads2() { int n = 4; int m = 6; int[] w = {0,1,2,3,2}; int[] v = {0,4,6,12,7};

    int[] dp = new int[7];

    for (int i = 1; i < 5; i++) {
        for (int j = 6; j >=w[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j-w[i]] + v[i]);
        }
        for (int t = 0; t < dp.length; t++) {
            System.out.print(dp[t]);
        }
        System.out.println();
    }
}

完全背包

题目地址

P1616

朴素处理方式:

基于01背包,在i,j确定时,不断增加此物品的数量并向前查询,时间复杂度O(n^3).

测试代码:

@Test
    void contextLoads3() {
        int n = 3;
        int m = 70;
        int[] w = {71,69,1};
        int[] v = {100,1,2};

        int[] dp = new int[71];

        for (int i = 0; i < 3; i++) {
            for (int j =70; j >= w[i] ; j--) {
                for (int k = 0; k <= m/w[i]&&(j-k*w[i]>=0); k++) {
                    dp[j] = Math.max(dp[j],dp[j-k*w[i]] + k*v[i]);
                }
            }
            for (int t = 0; t < dp.length; t++) {
                System.out.print(dp[t]);
            }
            System.out.println();
            }
        System.out.println("ans"+dp[70]);
        }

优化:

O(n^3) 的复杂度是无法承受的,可以想象的是:如果在i,j为特值的某一点,若不拿,则dp[i][j]=dp[i-1][j],若拿取,则dp[i][j] = dp[i][j-w[i]] + v[i],所以状态转移方程为:dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]),压缩后dp[j]=max(dp[j],dp[j-w[i]]+v[i]),与01背包相同,但是遍历顺序从前向后(从前向后用到本层数据,从后向前用到上一层数据)

优化代码:

@Test
    void contextLoads4() {
        int n = 3;
        int m = 70;
        int[] w = {71,69,1};
        int[] v = {100,1,2};

        int[] dp = new int[71];

        for (int i = 0; i < 3; i++) {
            for (int j =w[i]; j <=70 ; j++) {
                    dp[j] = Math.max(dp[j],dp[j-w[i]] + v[i]);
            }
            for (int t = 0; t < dp.length; t++) {
                System.out.print(dp[t]);
            }
            System.out.println();
        }
    }

问题解释:

为何01背包和完全背包的继承关系不同(dp[i][…],dp[i-1][…])?,也就是为什么01背包继承上层,完全背包继承本层?

实际上二者本质相同,如果01背包中存在相同元素,继承上层等同于完全背包的继承本层;二者关键区别是物品数量和遍历顺序,所以01背包对于一个元素,不存在递进关系,而完全背包本层加数量时可以递进.

多重背包

多重背包可以转化为01背包问题,对于不同数量的元素,使用二进制转化,可以使得原本s种选择转为log(s)次选择,主要变动在于处理输入数据上,而非核心算法,故不详细说明 ​