企业官网建设流程全解析

概述

前面两篇我们已经讲了动态规划的基础思路和线性 DP。

如果说线性 DP 主要训练的是：

沿着一条线往前推

那么背包问题训练的就是：

在有限容量里做选择

背包问题非常经典，也非常容易让初学者卡住。原因不在于代码多复杂，而在于它同时考察三件事：

• 状态怎么定义
• 物品能不能重复选
• 一维优化时循环顺序怎么写

本篇重点讲两个最基础、最重要的模型：

1. 01 背包
2. 完全背包

学完这篇，你应该能分清 01 背包和完全背包，并能独立写出二维 DP、一维优化和循环顺序。

核心概念：什么是背包问题

背包问题通常有这样一个背景：

有一个容量为bagSize的背包，有若干物品，每个物品有重量和价值，问在容量限制内能获得的最大价值。

比如：

物品重量：1, 3, 4 物品价值：15, 20, 30 背包容量：4

你要决定哪些物品放进背包，让总重量不超过4，同时总价值最大。

背包问题的三个关键变量

• 物品下标i：当前考虑到第几个物品
• 背包容量j：当前背包最多还能装多少重量
• 状态值dp：在当前条件下能得到的最大价值

背包问题的本质

背包问题的本质不是“装东西”，而是“做选择”：

• 当前物品选不选
• 当前物品能不能重复选
• 选了之后容量怎么变化

背包 DP 的本质，是在容量限制下，枚举物品选择并保存最优结果。

01 背包：每个物品最多只能选一次

先看最经典的01 背包。

它的限制是：

每个物品只有一个，要么选，要么不选

所以叫01，意思是每个物品只有两种状态：

• 0：不选
• 1：选

问题示例

weights = [1, 3, 4] values = [15, 20, 30] bagSize = 4

可选方案包括：

• 选重量1的物品，价值15
• 选重量3的物品，价值20
• 选重量4的物品，价值30
• 选重量1 + 3的两个物品，价值15 + 20 = 35

所以最大价值是35。

01 背包二维 DP：先把状态定义清楚

初学背包时，建议先写二维 DP。

二维 DP 更容易理解，因为状态含义比较直观。

状态定义

定义：

dp[i][j] 表示从下标 0 到 i 的物品里任意选择，放进容量为 j 的背包，能得到的最大价值

这里有两个维度：

• i：考虑到哪个物品
• j：当前背包容量

状态转移

对于第i个物品，有两种选择。

1. 不选第 i 个物品

如果不选第i个物品，那么结果直接继承上一行：

dp[i][j] = dp[i - 1][j]

2. 选第 i 个物品

如果选第i个物品，前提是当前容量j放得下它。

选了之后，背包剩余容量是：

j - weights[i]

所以价值是：

dp[i - 1][j - weights[i]] + values[i]

合并转移

因此：

dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i] )

注意第二项只有在j >= weights[i]时才成立。

当前物品只有选和不选两种情况，选了就只能从上一层状态转移过来。

01 背包二维代码实现

classSolution{publicintzeroOneKnapsack(int[]weights,int[]values,intbagSize){intn=weights.length;int[][]dp=newint[n][bagSize+1];for(intj=weights[0];j<=bagSize;j++){dp[0][j]=values[0];}for(inti=1;i<n;i++){for(intj=0;j<=bagSize;j++){dp[i][j]=dp[i-1][j];if(j>=weights[i]){dp[i][j]=Math.max(dp[i][j],dp[i-1][j-weights[i]]+values[i]);}}}returndp[n-1][bagSize];}}

初始化为什么这样写

第一行dp[0][j]表示只考虑第0个物品。

如果容量j能装下第0个物品，那么最大价值就是values[0]。

所以：

for(intj=weights[0];j<=bagSize;j++){dp[0][j]=values[0];}

为什么返回dp[n - 1][bagSize]

因为我们最终要考虑所有物品，并且背包容量是bagSize。

所以答案就是：

dp[n - 1][bagSize]

二维 01 背包最重要的是看懂dp[i][j]代表“前 i 个物品在容量 j 下的最优解”。

01 背包一维优化：为什么可以压缩空间

观察二维转移：

dp[i][j] 只依赖 dp[i - 1][j] 和 dp[i - 1][j - weights[i]]

也就是说，第i行只依赖上一行。
因此可以把二维数组压缩成一维数组。

一维状态定义

定义：

dp[j] 表示容量为 j 的背包，当前能得到的最大价值

转移写成：

dp[j] = max(dp[j], dp[j - weights[i]] + values[i])

关键问题：为什么容量要倒序遍历

01 背包一维优化时，容量必须倒序遍历：

for(intj=bagSize;j>=weights[i];j--){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}

原因是：

每个物品只能选一次

如果正序遍历，dp[j - weights[i]]可能已经在本轮被当前物品更新过。
这样就会导致同一个物品被重复使用。

01 背包倒序遍历，是为了保证当前物品不会在同一轮被重复选择。

01 背包一维代码实现

classSolution{publicintzeroOneKnapsack(int[]weights,int[]values,intbagSize){int[]dp=newint[bagSize+1];for(inti=0;i<weights.length;i++){for(intj=bagSize;j>=weights[i];j--){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}}returndp[bagSize];}}

一维写法的理解方式

外层枚举物品，内层枚举容量。

对于每个物品，都尝试把它放进不同容量的背包里。
如果放进去能让价值更大，就更新dp[j]。

一维 01 背包的模板很短，但倒序遍历是不能改的核心规则。

完全背包：每个物品可以选无限次

接着看完全背包。

它和 01 背包最关键的区别是：

每个物品可以重复选择

比如有一个重量为2、价值为5的物品，只要容量允许，就可以选多次。

问题示例

weights = [1, 3, 4] values = [15, 20, 30] bagSize = 4

如果每个物品可以无限选，那么最优方案可能是：

选 4 个重量为 1 的物品，总价值 60

这和 01 背包完全不同。

完全背包允许同一个物品重复使用，所以转移来源和循环顺序都会变化。

完全背包二维 DP：和 01 背包的关键差异

二维完全背包也可以这样定义：

dp[i][j] 表示从下标 0 到 i 的物品里任意选择，放进容量为 j 的背包，能得到的最大价值

不选第i个物品时：

dp[i][j] = dp[i - 1][j]

选第i个物品时，注意这里不是从dp[i - 1]转移，而是从dp[i]转移：

dp[i][j] = dp[i][j - weights[i]] + values[i]

因为第i个物品可以继续选。

合并转移

dp[i][j] = max( dp[i - 1][j], dp[i][j - weights[i]] + values[i] )

这里和 01 背包最大的区别是第二项：

01 背包选当前物品后看上一行，完全背包选当前物品后仍然可以看当前行。

完全背包一维代码实现

完全背包一维写法最常见，也最重要。

classSolution{publicintcompleteKnapsack(int[]weights,int[]values,intbagSize){int[]dp=newint[bagSize+1];for(inti=0;i<weights.length;i++){for(intj=weights[i];j<=bagSize;j++){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}}returndp[bagSize];}}

为什么完全背包容量要正序遍历

完全背包允许同一个物品重复选择。

所以我们希望dp[j - weights[i]]可以使用本轮已经更新过的结果。
这正好对应正序遍历。

如果倒序遍历，就会变成“当前物品只能用一次”，那就退化成 01 背包了。

完全背包正序遍历，是为了允许当前物品在同一轮被重复选择。

01 背包和完全背包的模板对比

这两个模板长得非常像，区别主要在内层循环方向。

01 背包模板

for(inti=0;i<n;i++){for(intj=bagSize;j>=weights[i];j--){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}}

完全背包模板

for(inti=0;i<n;i++){for(intj=weights[i];j<=bagSize;j++){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}}

对比表

判断背包类型时，先看物品能选几次，再决定容量循环方向。

组合问题和排列问题：循环顺序还有另一层含义

很多背包题不一定问最大价值，而是问方案数。

这时循环顺序还会影响“组合”和“排列”。

组合问题

如果不关心顺序，例如：

1 + 2 和 2 + 1 算同一种方案

通常先遍历物品，再遍历容量：

for(inti=0;i<nums.length;i++){for(intj=nums[i];j<=target;j++){dp[j]+=dp[j-nums[i]];}}

排列问题

如果关心顺序，例如：

1 + 2 和 2 + 1 算两种方案

通常先遍历容量，再遍历物品：

for(intj=1;j<=target;j++){for(inti=0;i<nums.length;i++){if(j>=nums[i]){dp[j]+=dp[j-nums[i]];}}}

为什么顺序会影响结果

因为dp[j]的更新顺序决定了方案是按“物品集合”统计，还是按“选择顺序”统计。

求组合通常物品在外，求排列通常容量在外。

常见题型：背包不一定长得像背包

很多题表面上看不出背包，但本质都是背包模型。

01 背包常见变形

• 每个数字只能用一次
• 选一些元素凑成目标和
• 把数组分成两个和相等的子集
• 每个物品只能选或不选

典型状态：

dp[j] 表示容量为 j 时的最优值或可行性

完全背包常见变形

• 硬币可以无限使用
• 数字可以重复选择
• 求凑成目标值的最少数量
• 求凑成目标值的方案数

典型状态：

dp[j] 表示凑成 j 的最优值、最少数量或方案数

只要题目出现“容量、目标值、选或不选、能否重复选”，就应该联想到背包。

背包问题的状态类型

背包不只可以求最大价值，还可以求很多不同目标。

是否可达示例

boolean[]dp=newboolean[target+1];dp[0]=true;for(intnum:nums){for(intj=target;j>=num;j--){dp[j]=dp[j]||dp[j-num];}}

这里倒序遍历，说明每个num只能用一次。

最少数量示例

int[]dp=newint[amount+1];Arrays.fill(dp,amount+1);dp[0]=0;for(intcoin:coins){for(intj=coin;j<=amount;j++){dp[j]=Math.min(dp[j],dp[j-coin]+1);}}

这里正序遍历，说明每个coin可以重复使用。

背包题先判断求什么，再决定dp[j]存最大值、布尔值、方案数还是最少数量。

常见问题点

1. 分不清 01 背包和完全背包

最核心的问题是：

当前物品能不能重复选？

如果不能重复选，就是 01 背包。
如果可以重复选，就是完全背包。

2. 一维优化时循环方向写反

这是最常见错误。

• 01 背包：容量倒序
• 完全背包：容量正序

3. 初始化不符合题意

不同问题初始化不同：

• 最大价值通常初始化为0
• 可行性问题通常dp[0] = true
• 方案数问题通常dp[0] = 1
• 最小值问题通常先填充一个较大值

4. 忘记判断容量是否够

二维写法里选当前物品时，一定要判断：

j >= weights[i]

一维写法可以通过循环起点规避这个问题。

5. 把组合数和排列数混在一起

求方案数时，一定要看题目是否关心顺序。

如果题目说[1, 2]和[2, 1]算不同方案，那就是排列。
如果只关心选了哪些数，那就是组合。

背包题大多数错误都来自类型判断、循环方向和初始化。

复杂度分析：背包 DP 的成本怎么看

设：

• 物品数量为n
• 背包容量为bagSize

二维写法

时间复杂度：

O(n * bagSize)

空间复杂度：

O(n * bagSize)

一维优化

时间复杂度仍然是：

O(n * bagSize)

空间复杂度优化为：

O(bagSize)

为什么时间没有变

因为物品和容量仍然都要枚举一遍。
一维优化只是减少了保存状态的空间。

背包 DP 通常是物品数乘容量，一维优化主要优化空间，不改变时间复杂度。

标准思考流程：遇到背包题应该怎么想

建议按下面顺序分析。

第一步：判断是不是背包

看题目里有没有这些关键词：

• 目标和
• 容量限制
• 选一些元素
• 每个元素能不能重复用
• 最大值、最小值、方案数、可行性

第二步：判断物品能选几次

只能选一次 -> 01 背包 可以无限选 -> 完全背包

第三步：定义dp[j]

想清楚：

dp[j] 表示什么？

它可能表示：

• 最大价值
• 是否能凑出
• 凑出方案数
• 最少使用数量

第四步：确定初始化

初始化一定要服务于dp[j]的含义。

第五步：确定循环顺序

01 背包：物品在外，容量倒序 完全背包：物品在外，容量正序 排列问题：容量在外，物品在内

背包题不要先背代码，先判断类型、状态、初始化和循环顺序。

模板总结

01 背包最大价值模板

int[]dp=newint[bagSize+1];for(inti=0;i<n;i++){for(intj=bagSize;j>=weights[i];j--){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}}returndp[bagSize];

完全背包最大价值模板

int[]dp=newint[bagSize+1];for(inti=0;i<n;i++){for(intj=weights[i];j<=bagSize;j++){dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);}}returndp[bagSize];

01 背包可行性模板

boolean[]dp=newboolean[target+1];dp[0]=true;for(intnum:nums){for(intj=target;j>=num;j--){dp[j]=dp[j]||dp[j-num];}}returndp[target];

完全背包最少数量模板

int[]dp=newint[amount+1];Arrays.fill(dp,amount+1);dp[0]=0;for(intcoin:coins){for(intj=coin;j<=amount;j++){dp[j]=Math.min(dp[j],dp[j-coin]+1);}}returndp[amount]>amount?-1:dp[amount];

背包模板看起来像几行代码，但每一行都对应着物品次数、状态含义和循环顺序。

总结

背包问题是动态规划里非常重要的一类题。
它的难点不是公式多，而是模型判断和循环顺序。

你可以重点记住下面几句话：

• 01 背包：每个物品最多选一次
• 完全背包：每个物品可以重复选
• 01 背包一维优化时容量倒序遍历
• 完全背包一维优化时容量正序遍历
• 最大价值、可行性、方案数、最少数量对应不同dp[j]含义
• 求组合通常物品在外，求排列通常容量在外
• 初始化必须和状态定义严格对应

背包问题刚开始学会觉得绕，但一旦把“能不能重复选”和“循环顺序”这两个点打通，很多题都会变成同一套模板的变形。