<—麻烦点一下这个

推荐一下$\color{#FF00FF}{算法基础课 第五章 动态规划全题解（正在完善）}$

更新过程：

• 2022.3.27 完成题解最初版本
• 2022.3.29

  发现键盘误$×2$，已订正
  发现语法失效错误$×2$，已修正
  更新七句话

• 2023.8.8

  发现一处错误，已订正
  并优化了$markdown$

题外话（还是忙人请跳过）：

大概的看了几篇赞数很高的题解，
发现大家都是把二维和滚动数组优化略讲或者直接省略
所以，我把前面这些二维数组和滚动数组的讲得比较详细
一维的没多少时间写了，毕竟其他题解也写得很好
所以一维的了解不了的话可以去逛逛其他的题解

求关注~

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

讲解一下题目：
这道题的题目比较好理解
重要的地方我都给大家标粗了~

关键词（和上面粗体字一致）：

每件物品只能使用一次
总体积不超过背包容量（不是正好相等哦~）
求的是总价值最大（不是最多能放多少个东西）
放进一个物品是能获得价值，不是白嫖，就像你看完我的题解不能白嫖一样，必须点个赞再走

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $vi,wi$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0<N,V≤1000$
$0<vi,wi≤1000$

算法1

(二维动态规划) $O(n^2)$

提前声明：v是体积，w是价值
如图：

时间复杂度

两层循环，$O(n^2)$

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N]; //每个物品的体积
int w[N]; //每个物品的价值
int f[N][N]; //状态转移方程，上面有详细解释
int main(){
    int n,m;
    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 ++){
            if(j < v[i]) f[i][j] = f[i - 1][j]; //不合法，不包括i
            else f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]); //包括i
        }
    }
    printf("%d",f[n][m]); //输出答案
    return 0;
}

开始简化代码（不是优化啊）
我们发现，凡是不包括$i$和包括i，都有$f[i - 1][j]$这个语句
可以合并

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N]; //每个物品的体积
int w[N]; //每个物品的价值
int f[N][N]; //状态转移方程，上面有详细解释
int main(){
    int n,m;
    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] = max(f[i][j],f[i - 1][j - v[i]] + w[i]); //已经把f[i][j]赋值为f[i - 1][j]了，现在就可以直接用f[i][j]了
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

算法2

(DP滚动数组优化) $O(n^2)$

注意：这里优化的是空间而不是时间

通过观察我们可以发现，我们状态转移只需要用到i和i - 1
于是，很自然的，$f[N][N]$就可以优化为$f[2][N]$啦~

这个比较好理解，只是优化空间，思路没多大变化，这里就不再单独画DP图了

优化内容如图：

那怎么覆盖掉前面没用的数组呢
（为什么我感觉这话像是在问刚学C艹的小朋友…）
我们可以使用$mod$（%）运算，也可以用$&$来实现
下面是使用& 1来实现滚动数组的代码（下面也有使用% 2的代码哦~）

注意：

不要把f[2][N]写成f[N][2]了（笑死我了我前面题解就写错了这样一个地方）
更新的是第二维哦~

时间复杂度

此处优化的是空间，时间没变，$O(n^2)$

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N];
int w[N];
int f[2][N];
int main(){
    int n,m;
    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 & 1][j] = f[i - 1 & 1][j];
            if(j >= v[i]) f[i & 1][j] = max(f[i & 1][j],f[i - 1 & 1][j - v[i]] + w[i]);
        }
    }
    printf("%d",f[n & 1][m]);
    return 0;
}

使用%运算：

注意：

上面$-$的优先级高于$&$运算，所以$i - 1 & 1$的$i - 1$不用括号
但是$%$运算的优先级高于$-$运算，所以一定要加括号，不然你就等着好看的$Wrong Answer$吧

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N];
int w[N];
int f[N][N];
int main(){
    int n,m;
    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 % 2][j] = f[(i - 1) % 2][j];
            if(j >= v[i]) f[i % 2][j] = max(f[i % 2][j],f[(i - 1) % 2][j - v[i]] + w[i]);
        }
    }
    printf("%d",f[n % 2][m]);
    return 0;
}

我在这里想说的是，我们滚动数组优化后的空间复杂度比一维数组的空间复杂度大了$2$倍
但是在计算时，这多出的$2$倍没有多大区别
所以大家如果一维的不太理解的话，可以试着用这个算法，空间复杂度不会差多少。

算法3

(一维数组DP) $O(n^2)$

（如果这一段看不懂的话可以看代码后的解释）
我们发现，我们在做$i$个数的时候，只用到了$i - 1$
且不管包含$i$里的$j - v[i]$，还是不包含$i$里的$j$都是小于等于$j$的
所以，可以优化成一维数组
如图：

那怎么在原来二维数组的基础上修改呢？
我们只需要去掉第一维，再把第二层$for$循环改成从$m$ 到 $0$就可以了

时间复杂度

此处优化的还是空间，时间没变，$O(n^2)$

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i ++) cin>>v[i]>>w[i];
    for(int i = 1;i <= n;i ++){
        for(int j = m;j >= v[i];j --){ //递推
            f[j] = max(f[j],f[j - v[i]] + w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

这里再讲解一下吧。
可能这个会讲得更清楚些，不过你理解了上面的那段这里就不用看了。

其实仔细看过代码很好理解的。

首先我们看二维的状态转移方程：

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

那么去掉第一维后：

$$f[j] = max(f[j],f[j - v[i]] + w[i]$$

在二维的状态转移方程中，$max$中只调用了$f$第一维中的$i - 1$行。
在做这个$max$的时候，很明显$f[i]$这一行还未被更新过。
那么他存储的就是$f[i - 1]$这一行的值。
所以，去掉第一维后，状态转移方程是对的。

$v[]$数组和$w[]$数组就不用说了，值是不变的，而且用的是第$i$行。

（共$270$行）