[leetcode/lintcode 题解] 背包问题
在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为 m，每个物品的大小为 A[i]。
- 你不可以将物品进行切割。
样例 1: 输入: [3,4,8,5], backpack size=10 输出: 9 样例 2: 输入: [2,3,5,7], backpack size=12 输出: 12 算法：DP
从已知的题目中，可以总结出以下两点：
- 每件物品只有一种
- 每件物品最多选择一次
那么考虑对于前 i 件的物品在容量为 w 的背包下，最大的装载量是多少，由此可以总结出对应的子结构，进行动态规划。
算法思路
设计 dp 数组 dp[n][m]，用 dp[i][j]表示第 i 个物品在容量为 j 的背包下，最大的装载量。
在这个问题中，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前 i−1 件物品的问题：
- 如果不放第 i 件物品，可得 dp[i][j]=dp[i−1][j]
- 如果放了第 i 件物品，可得 dp[i][j]=dp[i−1][j−A[i]]+Ai
总结状态转义方程为：dp[i][j]=max(dp[i−1][j],dp[i−1][j−A[i]]+A[i])
复杂度分析
n 表示物品件数，m 表示背包容量
- 时间复杂度：O(nm)
- 空间复杂度：O(nm)
算法优化观察上方的状态转义方程，可以发现 dp[i][j]方程的两个状态都只和 dp[i-1]有关，显然通过 O(nm)的空间复杂度，难免会浪费一些空间。
可以考虑使用滚动数组优化，建立 dp 数组 dp[m]，使用 dp[j-A[i]]代替 dp[i-1][j-A[i]]。优化后状态转义方程为 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-v2ex-fks
字节抖音组大牛 2 小时剖析目前大热的 [秒杀系统和订单系统] ，通过分析高并发场景下的常见问题了解数据一致性，什么是动静分离，读写分离如何实现，如何防止超卖等秒杀系统设计的核心考点。
课程亮点
通过秒杀系统和订票系统了解如下内容：
- 高并发场景下引发的常见问题
- 了解数据一致性
- 什么是动静分离
- 读写分离如何实现
- 如何防止超卖
讲师介绍
西毒——就职于国内一线互联网企业，服务于亿级日活用户。擅长后端服务开发和架构设计。同时有丰富的面试经验，面试过近百位候选人。
讲座时间：8/22 （本周六）上午 10:00:00
报名方式:
戳我即可报名