经典背包系列问题

时间:2022-11-02 19:09:15

作者:Grey

原文地址:

博客园:经典背包系列问题

CSDN:经典背包系列问题

问题一

题目描述

在 n 个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为Ai (每个物品只能选择一次且物品大小均为正整数)

题目链接:LintCode 92 · Backpack

暴力递归方法思路

定义递归函数

int p(int rest, int i, int[] arr)

递归含义表示:从 i 开始到最后,还剩下 rest 容量的情况下,得到的最大值是多少。

递归函数中有两个决策,第一个决策,不要当前位置物品


int p1 = p(rest, i+1, arr);

第二个决策,要当前物品,这个决策下,有一个限制条件,即当前物品大小不超过 rest,

arr[i] + p(rest - arr[i], i + 1, arr)

暴力解法的完整代码如下

public class Solution {

    public static int backPack(int m, int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        return p(m, 0, arr);
    }

    public static int p(int i, int j, int[] arr) {
        if (j == arr.length) {
            return 0;
        }
        int p1 = p(i, j + 1, arr);
        return i >= arr[j] ? Math.max(arr[j] + p(i - arr[j], j + 1, arr), p1) : p1;
    }
}

超时

经典背包系列问题

优化一,可以通过缓存法来对上述递归过程进行优化,由于递归函数只有两个可变参数,所以可以定义一个二维数组 dp,二维数组的元素全部初始化为 -1,表示未计算过,用这个二维数组就可以存下所有的递归过程中间值,在递归函数中,如果 dp 的值已经计算过,直接返回即可。在每次递归结果返回之前,要先把结果存入 dp 对应的位置,缓存法的完整代码和注释说明如下:

public class Solution {

    public static int backPack(int m, int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][m + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return p2(m, 0, arr, dp);
    }

    public static int p2(int rest, int i, int[] arr, int[][] dp) {
        // 计算过,直接返回即可
        if (dp[i][rest] != -1) {
            return dp[i][rest];
        }
        int ans = 0;
        if (i == arr.length) {
            // 每次计算的结果在返回之前,先更新 dp 值
            dp[i][rest] = ans;
            return ans;
        }
        int p1 = p2(rest, i + 1, arr, dp);
        ans = rest >= arr[i] ? Math.max(arr[i] + p2(rest - arr[i], i + 1, arr, dp), p1) : p1;
        // 每次计算的结果在返回之前,先更新 dp 值
        dp[i][rest] = ans;
        return ans;
    }
}

可 AC。

优化二,除了上述缓存法,也可以将暴力递归方法直接改成严格位置依赖的动态规划,设置一个 dp 数组

int[][] dp = new int[arr.length + 1][m + 1]

其中 dp[i][j] 就表示递归函数 p(i,j,arr) 的值,根据暴力递归方法可知

dp[i][j] 依赖的位置是 dp[i][j+1] 以及 dp[i - arr[j]][j + 1] 两个位置的值,完整代码如下

public class Solution {

    public static int backPack(int m, int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int[][] dp = new int[arr.length + 1][m + 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < m + 1; j++) {
                int p1 = dp[i + 1][j];
                dp[i][j] = j >= arr[i] ? Math.max(arr[i] + dp[i + 1][j - arr[i]], p1) : p1;
            }
        }
        return dp[0][m];
    }
}

可 AC。

优化三,上述动态规划的转移过程如下

经典背包系列问题

其中 dp[i][j] 依赖的位置是 dp[i][j+1] 以及 dp[i - arr[j]][j + 1] 两个位置,根据这个依赖关系,可以将二维数组简化成一维数组,

设置一维数组

int[] dp = new int[m + 1];

先求最后一列的值,然后复用这个数组推出倒数第二列的值。最后推到第一列的值,完整代码

public class Solution {

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

问题二

问题描述

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值,问最多能装入背包的总价值是多大?

题目链接:LintCode 125 · Backpack II

暴力解法

定义递归函数

int process(int i, int m, int[] w, int[] v)

递归含义表示:i 号及其往后所有的物品在重量允许范围内的最大价值是多少。

首先是 base case

        if (i == w.length) {
            return 0;
        }

表示无物品可选,返回 0 的价值。

接下来是普遍情况,有两种决策,

决策一:选择 i 位置的物品,则

int p1 = process(i + 1, m, w, v);

决策二,不选择 i 位置的物品,此时有条件,即物品重量不能超过当前书包的剩余容量,即

v[i] + process(i + 1, m - w[i], w, v)

完整代码如下

public class Solution {

    public static int backPackII(int m, int[] w, int[] v) {
        if (m <= 0 || w == null || w.length < 1 || v == null || v.length < 1) {
            return 0;
        }
        return process(0, m, w, v);
    }

    // i号及其往后所有的物品在重量允许范围内的最大价值是多少
    public static int process(int i, int m, int[] w, int[] v) {
        if (i == w.length) {
            return 0;
        }
        // 不选i号商品
        int p1 = process(i + 1, m, w, v);
        if (m >= w[i]) {
            // 这种情况下,才有资格选i号商品
            return Math.max(p1, v[i] + process(i + 1, m - w[i], w, v));
        }
        return p1;
    }
}

超时

经典背包系列问题

优化一,增加缓存,使用一个二维数组 dp 来存储递归过程的中间值

int[][] dp = new int[w.length + 1][m + 1];

dp 的初始值全为 -1, 同时,将每次递归结果都存入 dp 中,如果某个递归算过了,则直接返回即可,完整代码如下


public class Solution {

    public static int backPackII(int m, int[] w, int[] v) {
        if (m <= 0 || w == null || w.length < 1 || v == null || v.length < 1) {
            return 0;
        }
        int[][] dp = new int[w.length + 1][m + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(0, m, w, v, dp);
    }

    public static int process2(int i, int m, int[] w, int[] v, int[][] dp) {
        if (dp[i][m] != -1) {
            return dp[i][m];
        }
        if (i == w.length) {
            dp[i][m] = 0;
            return 0;
        }
        // 最后一行都是0
        // 从最后一行开始
        int ans = process2(i + 1, m, w, v, dp);
        if (i < w.length && m >= w[i]) {
            // 这种情况下,才有资格选i号商品
            ans = Math.max(ans, v[i] + process2(i + 1, m - w[i], w, v, dp));
        }
        dp[i][m] = ans;
        return ans;
    }
}

可 AC

优化二,由于暴力递归过程只有两个可变参数,所以本问题也可以改成严格位置的动态规划解,定义一个二维数组 dp,

int[][] dp = new int[w.length + 1][m + 1];

通过观察暴力递归过程可知,dp[i][j] 依赖 dp[i+1][j]dp[i+1][j-w[i]] 两个位置的值,完整代码如下

public class Solution {

    public static int backPackII(int m, int[] w, int[] v) {
        if (m <= 0 || w == null || w.length < 1 || v == null || v.length < 1) {
            return 0;
        }
        int[][] dp = new int[w.length + 1][m + 1];
        // 倒数第一行都是0
        // 从倒数第二行开始填
        for (int i = w.length - 1; i >= 0; i--) {
            for (int j = m; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (j >= w[i]) {
                    dp[i][j] = Math.max(dp[i][j], v[i] + dp[i + 1][j - w[i]]);
                }
                if (j == m && i == 0) {
                    break;
                }
            }
        }
        return dp[0][m];
    }
}

优化四,参考问题1,上述动态规划也可以做进一步的空间压缩,使用一个一维数组来滚动更新,不赘述,完整代码如下

public class Solution {

        public static int backPackII(int m, int[] w, int[] v) {
        if (m <= 0 || w == null || w.length < 1 || v == null || v.length < 1) {
            return 0;
        }
        int[] dp = new int[m + 1];
        for (int i = w.length - 1; i >= 0; i--) {
            for (int j = m; j >= 0; j--) {
                if (j >= w[i]) {
                    dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
                }
                if (i == 0) {
                    break;
                }
            }
        }
        return dp[m];
    }
}

更多

算法和数据结构笔记