XinXin星星

用户名：aizim

访问量：281

签　名：

等　　级
排　　名	39320
经　　验	338
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

在01背包问题中，dp算法做了什么
浏览：264

你可能喜欢

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

在01背包问题中，dp算法做了什么

　　作者: XinXin星星　　　　发表时间：2021-11-03 18:27:33 浏览：264　|　评论：0　

在写这一片博客的时候，我抱着和大家一起学习的心态，发表一些自己的看法，希望有小伙伴能够主动提出我的不足。
下面进入正题...
## 变量

```cpp
const int MAX = 1000;
int f[MAX][MAX];
int v[MAX],w[MAX];
int n, k;
```
第一行的**const**定义常量，第二行**v[]**、**w[]**表示物品的体积和价值，第三行的**f[][]**表示函数**f(n,k)**，第四行**n**表示定义物品的数量，**k**表示背包所能容纳的最大体积。

**f(n,k)**所代表的是一个函数，若**n**为4，**k**为5。

四个物品的体积为：1  2  3   4      价值为：2  4  4  5。

那么**f(4,5)**的值为8，这个值是如何得来的？通过推到的方式找出8的值，我们可以从四号物品开始推导若**选择了四号物品**，那么仔细对比一下发现，无法选择出最大值，在此次推导的过程中，我们把**选择四号物品和不选择四号物品进行了一次比较**。

如果**不选择四号物品**，那么就**选择三号物品**，选择了三号物品发现有两个结果，第一个是和二号物品组成价值结果8，第二个是和一号物品组成价值结果6，这个过程，是**选择三号物品当中，再与第一个物品或第二个物品进行了比较**。

上述可以发现，我们其实并不是像数学一样求函数，而是**创建一个变量**，一次一次的比较，找出最大的值。
##函数f(n,v)的作用

![](/image_editor_upload/20211103061643_52332.png)
以上是整个过程的推导图，若计算机按照此推导图进行，即可出现答案。

但是很多同学就卡在这个地方，如何将这个推导的过程通过代码实现？本人刚开始看到这个推导图的时候也是一头雾水，实际上，这样给出的思路是**人性化**的，具有**跳跃性**。
但是仔细思考了一会，这个推导过程不能从上面讲的方式开始一步一步实现代码，而是**从最底层反推到最高层**，**f(4,5)**是通过比较下面的**f(3,1)+5**和**f(3,5)**但是这些数据**是空的**，做到下一层的时候就卡死了。所以应该从最底层开始对比大小，比完最底层的大小之后，就有数据**支撑**下一层的的对比大小，这样才是**正确的编程思路**。
## 实现代码
如果确认了角度，**f(n,v)**的值就是比较**f(n-1,[0~k])和f(n-1,[0~k]-v[n-1])+w[n-1](n-1号物品的价值)**进行比较,有了第一层的数据作为支撑。代码为
```cpp
f[n][k] = max(f[n-1][k],f[n-1][k-v[n-1]]+w[n-1]);
```
而如果剩余的体积**没办法容纳**此物品，则需要在下一层的结果进行覆盖代码为
```cpp
f[n+1][k] = f[n][k];
```
**判断条件**为：
```cpp
if(k<v[i])
```
而从第一步开始推导的的是**f[1][k]=max(f[0][k],f[0][k-v[0]]+w[0])**，下一步就是算出**f[2][k],f[3][k].....**

所以需要循环语句，**f[n][k]**的**n**从0开始递增到最顶层，而**k**也要创建一个循环，以此找出所有的**剩余背包容量**的结果，比较最大值。

当两个循环都进行完毕以后，输出**f[n][k]**就算顶层的最终答案。
##原代码
```cpp
int dp()
{
 
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if (j < v[i])f[i + 1][j] = f[i][j];
			else f[i + 1][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
		}
	}
	return 0;
}
```
感谢大家收看，如果喜欢的话，请点赞支持一下，我还会持续更新此系列，不仅自己学习，也方便记录自己的思路，和大家一起讨论

0.0分

6 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

XinXin星星

TA的其他文章

你可能喜欢

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

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

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

字符逆序（C语言代码）

上车人数（C语言代码）

在01背包问题中，dp算法做了什么

评论区

精彩推荐

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

C二级辅导-等差数列（C++代码）

C二级辅导-等差数列（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符串问题（C语言代码）

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

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

淘淘的名单（C语言代码）

XinXin星星

TA的其他文章

你可能喜欢

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

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

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

字符逆序 （C语言代码）

上车人数 （C语言代码）

在01背包问题中，dp算法做了什么

评论区

精彩推荐

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

C二级辅导-等差数列 （C++代码）

C二级辅导-等差数列 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符串问题 （C语言代码）

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

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

淘淘的名单 （C语言代码）

字符逆序（C语言代码）

上车人数（C语言代码）

　　评论区

C二级辅导-等差数列（C++代码）

C二级辅导-等差数列（C语言代码）

字符串问题（C语言代码）

淘淘的名单（C语言代码）