mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
215 lines
6.7 KiB
Markdown
215 lines
6.7 KiB
Markdown
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
# 完全背包-一维数组
|
||
|
||
本题力扣上没有原题，大家可以去[卡码网第52题](https://kamacoder.com/problempage.php?pid=1052)去练习。
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[带你学透完全背包问题！ ](https://www.bilibili.com/video/BV1uK411o7c9/)，相信结合视频再看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
|
||
## 思路
|
||
|
||
本篇我们不再做五部曲分析，核心内容 在 01背包二维 、01背包一维 和 完全背包二维 的讲解中都讲过了。
|
||
|
||
上一篇我们刚刚讲了完全背包二维DP数组的写法：
|
||
|
||
```CPP
|
||
for (int i = 1; i < n; i++) { // 遍历物品
|
||
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
|
||
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
|
||
else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
|
||
}
|
||
}
|
||
```
|
||
|
||
压缩成一维DP数组，也就是将上一层拷贝到当前层。
|
||
|
||
将上一层dp[i-1] 的那一层拷贝到 当前层 dp[i] ，那么 递推公式由：`dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])` 变成： `dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])`
|
||
|
||
这里有录友想，这样拷贝的话， dp[i - 1][j] 的数值会不会 覆盖了 dp[i][j] 的数值呢？
|
||
|
||
并不会，因为 当前层 dp[i][j] 是空的，是没有计算过的。
|
||
|
||
变成 `dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])` 我们压缩成一维dp数组，去掉 i 层数维度。
|
||
|
||
即：`dp[j] = max(dp[j], dp[j - weight[i]] + value[i])`
|
||
|
||
|
||
接下来我们重点讲一下遍历顺序。
|
||
|
||
看过这两篇的话：
|
||
|
||
* [01背包理论基础（二维数组）](https://programmercarl.com/背包理论基础01背包-1.html)
|
||
* [01背包理论基础（一维数组）](https://programmercarl.com/背包理论基础01背包-2.html)
|
||
|
||
就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
|
||
|
||
**在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的**！
|
||
|
||
因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
|
||
|
||
遍历物品在外层循环，遍历背包容量在内层循环，状态如图：
|
||
|
||
|
||
|
||
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：
|
||
|
||
|
||
|
||
看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）。
|
||
|
||
先遍历背包再遍历物品，代码如下：
|
||
|
||
```CPP
|
||
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
|
||
for(int i = 0; i < weight.size(); i++) { // 遍历物品
|
||
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
|
||
}
|
||
cout << endl;
|
||
}
|
||
```
|
||
|
||
先遍历物品再遍历背包：
|
||
|
||
```CPP
|
||
for(int i = 0; i < weight.size(); i++) { // 遍历物品
|
||
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
|
||
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
|
||
}
|
||
}
|
||
```
|
||
|
||
整体代码如下：
|
||
|
||
```cpp
|
||
#include <iostream>
|
||
#include <vector>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
int N, bagWeight;
|
||
cin >> N >> bagWeight;
|
||
vector<int> weight(N, 0);
|
||
vector<int> value(N, 0);
|
||
for (int i = 0; i < N; i++) {
|
||
int w;
|
||
int v;
|
||
cin >> w >> v;
|
||
weight[i] = w;
|
||
value[i] = v;
|
||
}
|
||
|
||
vector<int> dp(bagWeight + 1, 0);
|
||
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
|
||
for(int i = 0; i < weight.size(); i++) { // 遍历物品
|
||
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
|
||
}
|
||
}
|
||
cout << dp[bagWeight] << endl;
|
||
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
|
||
|
||
## 总结
|
||
|
||
细心的同学可能发现，**全文我说的都是对于纯完全背包问题，其for循环的先后循环是可以颠倒的！**
|
||
|
||
但如果题目稍稍有点变化，就会体现在遍历顺序上。
|
||
|
||
如果问装满背包有几种方式的话？ 那么两个for循环的先后顺序就有很大区别了，而leetcode上的题目都是这种稍有变化的类型。
|
||
|
||
这个区别，我将在后面讲解具体leetcode题目中给大家介绍，因为这块如果不结合具题目，单纯的介绍原理估计很多同学会越看越懵！
|
||
|
||
别急，下一篇就是了！
|
||
|
||
最后，**又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后再问，两个for循环的先后是否可以颠倒？为什么？**
|
||
|
||
这个简单的完全背包问题，估计就可以难住不少候选人了。
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### Java：
|
||
|
||
```java
|
||
import java.util.Scanner;
|
||
|
||
public class Main {
|
||
public static void main(String[] args) {
|
||
Scanner scanner = new Scanner(System.in);
|
||
int N = scanner.nextInt();
|
||
int bagWeight = scanner.nextInt();
|
||
|
||
int[] weight = new int[N];
|
||
int[] value = new int[N];
|
||
for (int i = 0; i < N; i++) {
|
||
weight[i] = scanner.nextInt();
|
||
value[i] = scanner.nextInt();
|
||
}
|
||
|
||
int[] dp = new int[bagWeight + 1];
|
||
|
||
for (int j = 0; j <= bagWeight; j++) { // 遍历背包容量
|
||
for (int i = 0; i < weight.length; i++) { // 遍历物品
|
||
if (j >= weight[i]) {
|
||
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
|
||
}
|
||
}
|
||
}
|
||
|
||
System.out.println(dp[bagWeight]);
|
||
scanner.close();
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
|
||
|
||
### Python：
|
||
|
||
```python
|
||
def complete_knapsack(N, bag_weight, weight, value):
|
||
dp = [0] * (bag_weight + 1)
|
||
|
||
for j in range(bag_weight + 1): # 遍历背包容量
|
||
for i in range(len(weight)): # 遍历物品
|
||
if j >= weight[i]:
|
||
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
|
||
|
||
return dp[bag_weight]
|
||
|
||
# 输入
|
||
N, bag_weight = map(int, input().split())
|
||
weight = []
|
||
value = []
|
||
for _ in range(N):
|
||
w, v = map(int, input().split())
|
||
weight.append(w)
|
||
value.append(v)
|
||
|
||
# 输出结果
|
||
print(complete_knapsack(N, bag_weight, weight, value))
|
||
|
||
|
||
```
|
||
|
||
|
||
### Go：
|
||
|
||
```go
|
||
|
||
```
|
||
### Javascript:
|
||
|
||
```Javascript
|
||
```
|
||
|