LintCode领扣 题解丨大厂经典动态规划:背包问题

在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。

你不可以将物品进行切割。
在线评测地址:
https://www.lintcode.com/problem/backpack/?utm_source=sc-tianchi-sz0821

样例 1:

输入:  [3,4,8,5], backpack size=10
输出:  9

样例 2:

输入:  [2,3,5,7], backpack size=12
输出:  12

算法:DP

从已知的题目中,可以总结出以下两点:

每件物品只有一种
每件物品最多选择一次
那么考虑对于前i件的物品在容量为w的背包下,最大的装载量是多少,由此可以总结出对应的子结构,进行动态规划。

算法思路

设计dp数组dpn,用dpi表示第i个物品在容量为j的背包下,最大的装载量。

在这个问题中,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i−1件物品的问题:

如果不放第i件物品,可得dpi=dpi−1
如果放了第i件物品,可得dpi=dpi−1]+Ai
总结状态转义方程为:dpi=max(dpi−1,dpi−1]+A[i])

复杂度分析

n表示物品件数,m表示背包容量

时间复杂度:O(nm)
空间复杂度:O(nm)
算法优化观察上方的状态转义方程,可以发现dpi方程的两个状态都只和dp[i-1]有关,显然通过O(nm)的空间复杂度,难免会浪费一些空间。

可以考虑使用滚动数组优化,建立dp数组dp[m],使用dp[j-A[i]]代替dpi-1]。优化后状态转义方程为dp[j]=max(dp[j],dp[j−A[i]]+A[i])

优化后复杂度分析

时间复杂度:O(nm)

空间复杂度:O(m)

代码思路分析

建立数组dp[m]表示背包容量为m的情况下,最大的装载量
初始化dp[0]=0
正序枚举A[i],并倒叙枚举j,这样所需要的dp[j-A[i]]不会被提前更新
最后返回dp[m],表示背包容量在m下的答案
public class Solution {

/**
 * @param m: An integer m denotes the size of a backpack
 * @param A: Given n items with size A[i]
 * @return: The maximum size
 */
public int backPack(int m, int[] A) {
    // write your code here
    // 如果背包容量或者物品数量为0,则直接返回
    if (A.length == 0 || m == 0) {
        return 0;
    }
    int n = A.length;
    int[] dp = new int[m + 1];
    for (int i = 0; i < n; i++) {
        // 滚动数组优化 倒序枚举j
        for (int j = m; j >= A[i]; j--) {
            dp[j] = Integer.max(dp[j], dp[j - A[i]] + A[i]);
        }
    }
    return dp[m];
}

}
更多大厂面试动态规划题解参见九章算法官网:
https://www.jiuzhang.com/course/76/?utm_source=sc-tianchi-sz0821

上一篇:读透《阿里巴巴数据中台实践》,其到底有什么高明之处?


下一篇:如何在本地编译Fabric Code