XinXin星星

用户名：aizim

访问量：297

签　名：

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

　　自我简介：

TA的其他文章

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

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

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

　　作者: XinXin星星　　　　发表时间：2021-11-03 18:27:33 浏览：277　|　评论：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 人评分

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

XinXin星星

TA的其他文章

你可能喜欢

统计字符（C语言描述运用ctype.h）

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

【偶数求和】（C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

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

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

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

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

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

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

WU-输出正反三角形（C++代码）

求圆的面积（C语言代码）

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

XinXin星星

TA的其他文章

你可能喜欢

统计字符 （C语言描述运用ctype.h）

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

【偶数求和】 （C语言代码）记得sum的归零时机

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

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

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

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

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

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

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

WU-输出正反三角形 （C++代码）

求圆的面积 （C语言代码）

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

统计字符（C语言描述运用ctype.h）

【偶数求和】（C语言代码）记得sum的归零时机

　　评论区

WU-输出正反三角形（C++代码）

求圆的面积（C语言代码）