列公子

用户名：lielielie

访问量：10578

签　名：

等　　级
排　　名	1691
经　　验	2704
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯特殊的质数肋骨 DFS
浏览：306

蓝桥杯摆动序列 DFS -
浏览：425

蓝桥杯金陵十三钗 DFS + 剪枝
浏览：339

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

1924题 - 01背包 - 动态规划 + 一维数组空间优化

　　作者: 列公子　　　　发表时间：2020-03-19 16:34:27 浏览：535　|　评论：0　

原题链接：蓝桥杯算法提高VIP-01背包

# 01背包 动态规划 + 空间优化

## 思路

$$dp[i][j]$$ 表示考虑前$$i$$种物品, 背包容量为 $$j$$ 时的**最大价值**

转移方程:

$$dp[i][j] = max(dp[i - 1, j],  dp[i - 1][ j - w[i]] + v[i])$$

分别对应不装入物品$$i$$和装入物品$$i$$ 两种情况, 取其他的最大值

边界值:
$$dp[0][0] = 0$$

## 空间优化

由转移方程, 计算每个$$dp[i][j]$$ 只用到了 它**上方 及 左上**的元素, 则可以用一维数组优化, 也无需滚动数组。

$$dp[j]$$ 表示背包容量为$$j$$ 时的最大价值, 每次枚举**背包价值**时, **从大到小**遍历, 保证 ```dp[j - w]``` 未在此轮计算过, 即 ```dp[j - w]```依然属于 ```i-1``` 行

## 注意
```dp[]``` 有 **两种** 初始化方式
- ```dp[0] = 0``` ```dp[1...m] = -INF``` 
此时 ```dp[j]``` 为 背包容量**恰好**为 ```j``` 时的最优值。问题的最优值为```dp[1...m]``` 中的**最大值**, 即最后要**遍历**一次 ```dp[]```

- ```dp[0...m] = 0```
此时 ```dp[j]``` 为 背包容量**小于等于**```j``` 时的最优值。问题的最优值直接为 ```dp[m]```

## 完整代码 (AC) 初始化方式 1
```cpp
//
// 01背包 一维数组优化
//
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5010;
const int INF = 0x3f3f3f3f;

int n, m;       // 物品数, 背包容量
int dp[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	memset(dp, -0x3f, sizeof(dp));
	dp[0] = 0;
	
    cin >> n >> m;
	
	// 在线求解
    for (int i = 0; i < n; i ++){  // 枚举物品
        int v, w;       // 重量和价值
        cin >> v >> w;
		
        for (int j = m; j >= v; j --)  // 枚举背包容量, 注意从大到小枚举
            dp[j] = max(dp[j], dp[j - v] + w);
    }
    
	int ans = -INF;
	for (int i = 1; i <= m; i ++)
		ans = dp[i] > ans ? dp[i] : ans;
	
	cout << ans << endl;
    return 0;
}
```

## 完整代码 (AC) 初始化方式 2
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5010;

int n, m;       // 物品数, 背包容量
int dp[N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	memset(dp, 0, sizeof(dp));
	
    cin >> n >> m;
	
	// 在线求解
    for (int i = 0; i < n; i ++){  // 枚举物品
        int v, w;       // 重量和价值
        cin >> v >> w;
		
        for (int j = m; j >= v; j --)  // 枚举背包容量, 注意从大到小枚举
            dp[j] = max(dp[j], dp[j - v] + w);
    }
    	
	cout << dp[m] << endl;
    return 0;
}
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

1924题 - 01背包 - 动态规划 + 一维数组空间优化

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

P1001 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

母牛的故事（C语言代码）

列公子

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

字符串输入输出函数 （C++代码）（都当成字符串吧hhhhhhhh）

1924题 - 01背包 - 动态规划 + 一维数组空间优化

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

P1001 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

母牛的故事 （C语言代码）

C二级辅导-温度转换（C语言代码）

字符串输入输出函数（C++代码）（都当成字符串吧hhhhhhhh）

　　评论区

C二级辅导-阶乘数列（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

母牛的故事（C语言代码）