[//]: # 最简单的01背包问题(C语言)
二维代码
#include <stdio.h>
#include <stdlib.h>
#define N 1010
int n, m; // n为物品,m为背包体积
int v[N], w[N]; // v是对应物品体积,w是对应物品价值(权重,重量)
int f[N][N]; // dp的数组
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++) // 遍历物品
for (int j = 0; j <= m; j++) // 遍历体积
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = f[i][j] >= f[i - 1][j - v[i]] + w[i] ? f[i][j] : f[i - 1][j - v[i]] + w[i];
}
printf("%d\n", f[n][m]);
return 0;
}
*/
代码的巧妙地方
首先解释一下这个代码,最开始看视频的时候已经不知道f[][]是什么东西了,纠结于具体问题这个f应该怎么才能做出动态规划
解释完做基本的f二维数组里边存的是什么之后,看看代码
视频中在对全局变量进行创建的时候使用的是const int N中的N,但是C语言中const 就是用来限定一个变量不允许被改变的修饰符,即只读变量,因为占有存储空间,所以编译器不知道编译时的值,所以就不知道该给数组定义多大的。
C++中不存在这个问题
如果按const int N 来定义数组大小的话会报错 error:variably modified ‘v’ at file scope
所以用了#define
还有全局变量会自动初始化为0
c99标准:
If an object that has automatic storage duration is not initialized explicitly, its value isindeterminate. If an object that has static storage duration is not initialized explicitly,then:
— if it has pointer type, it is initialized to a null pointer;
— if it has arithmetic type, it is initialized to (positive or unsigned) zero;
— if it is an aggregate, every member is initialized (recursively) according to these rules;
— if it is a union, the first named member is initialized (recursively) according to theserules.
代码中
for (int i = 1; i <= n; i++) // 遍历物品
for (int j = 0; j <= m; j++) // 遍历体积
在循环的变量范围,首先i代表背包里选择1~i件物品放,这里一开始i初始化为1就是选1~1件,即1件,一直到最后i=n就是选择1~n件物品放入背包,这样从1开始也可以避免f[i-1][]当i=0的时候变成f[-1][]的出界问题,f[1][]可以直接从已经自动初始化的f[0][]进行计算
j需要从背包体积为0一直计算到背包的总体积m
算法整体思路见视频
一维代码
#include <stdio.h>
#include <stdlib.h>
#define N 1010
int n, m; // n为物品,m为背包体积
int v[N], w[N]; // v是对应物品体积,w是对应物品价值(权重,重量)
int f[N]; // dp的数组
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &v[i], &w[i]);
}
for (int i = 1; i <= n; i++) // 遍历物品
for (int j = m; j >= v[i]; j--) // 遍历体积
{
f[j] = f[j] >= f[j - v[i]] + w[i] ? f[j] : f[j - v[i]] + w[i];
}
printf("%d\n", f[m]);
return 0;
}
一维代码使用了滚动数组
这里我理解的就是之前的状态计算方程是f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]),这里边可以看出来第i行的dp数组仅仅与前一行有关
计算结果的保存都用一个一维数组就够了,所以dp数组f[][]中只剩下f[j]就够了
比如要算第二行的时候有第一行的数据就行了,算出来第二行后第一行可以丢掉了,通过第二行继续算第三行,这样其实只需要一维数组就行了
因为之前二维数组计算max的时候都需要f[i-1][j-v[i]]+w[i]与f[i-1][j]进行比较,f[i-1][j]也就是与前一行的这列的数,所以把前一行算出来的结果(一维)看作后一行的没比较的数据(一维),再通过这个一维的数据进行对应行的计算
假设这里一维的计算是之前二维计算时通过第二行的结果算第三行,目前的一维数组是第二行(i=2)的结果(一维),可以先将它当作第三行没比较之前的数(一维),然后通过现在没比较过的第三行的数据(其实就是第二行的数据,i=2)计算i=3时的f[j-v[i]]+w[i](也就是之前二维数组i=3时的f[i-1][j-v[i]]+w[i]),再与第二行的结果比较大小存入数组
这里的难点在于为什么j循环里边是倒着算的