背包问题
背包🎒是经典的 $DP$ 问题，而 $DP$ 问题的本质就是根据子问题的解以得出原问题的解。
$01$ 背包问题
[HTML_REMOVED]
有 $N$ 个物品和一个容量为 $V$ 的背包，每个物品有重量 $v_i$ 和价值 $w_i$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
回溯算法
对于这 $N$ 个物品，每一个物品都有选和不选两种选择，因此本问题可以使用 回溯求指数型枚举 的方法解决，但时间复杂度是 $O(2^n)$，不能接受。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int M = 1010;
int N, V;
int v[M], w[M];
int arr[M];
int mv = 0;
int mw = 0;
int res = 0;
void dfs(int i) {
if (mv + v[i] > V || i > N) {
if (res < mw) {
res = mw;
}
return ;
}
// select
mv += v[i];
mw += w[i];
dfs(i + 1);
mv -= v[i];
mw -= w[i];
// not select
dfs(i + 1);
}
int main() {
cin >> N >> V;
for (int i = 1; i <= N; i++) {
cin >> v[i] >> w[i];
}
dfs(1);
cout << res << endl;
return 0;
}
动态规划
我们首先定义 $f(i,j)$ 表示当前的状态，他表示对于前 $i$ 个物品，容量不超过 $j$ 的最大价值。
状态转移方程
[HTML_REMOVED]
由此我们可以得出我们的状态转移方程：
$$
f[i,\space j] = max(f[i-1,\space j],\space f[i-1,\space j -v_i]+w_i)
$$
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1010;
int N, V;
int v[M], w[M];
int f[M][M];
int main() {
cin >> N >> V;
for (int i = 1; i <= N; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i-1][j];
if (j >= v[i]) // 如果当前状态可以放下第 i 件物品
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);
}
}
cout << f[N][V] << endl;
return 0;
}
优化
我们可以看到第 $i$ 层状态只和第 $i-1$ 层状态有关。所以我们可以使用滚动数组的概念进行优化，把二维状态变为一维状态。
$$
f[j] = max(f[j],\space f[j -v_i]+w_i)
$$
for (int i = 1; i <= N; i++) {
for (int j = v[i]; j <= V; j++) {
// f[j] = f[j];
// if (j >= v[i]) // 如果当前状态可以放下第 i 件物品
f[j] = max(f[j], f[j-v[i]] + w[i]);
}
}
需要注意的一点是，我们如果这样写的话是从左到右进行更新。此时 $f[j-v[i]]$ 使用的是已经更新过的（即第 $i$ 层的状态），不是我们所需要的第 $i-1$ 层的状态。所以我们可以从右向左更新状态，使用的是第 $i-1$ 层的状态。
for (int i = 1; i <= N; i++) {
for (int j = V; j >= v[i]; j--) {
// f[j] = f[j];
// if (j >= v[i]) // 如果当前状态可以放下第 i 件物品
f[j] = max(f[j], f[j-v[i]] + w[i]);
}
}
完全背包问题
[HTML_REMOVED]
有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
回溯算法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int M = 1010;
int N, V;
int v[M], w[M];
int arr[M];
int mv = 0;
int mw = 0;
int res = 0;
void dfs(int i) {
if (mv + v[i] > V || i > N) {
if (res < mw) {
res = mw;
}
return ;
}
for (int k = 0; k * v[i] + mv <= V; k++) {
mv += k * v[i];
mw += k * w[i];
dfs(i + 1);
mv -= k * v[i];
mw -= k * w[i];
}
}
int main() {
cin >> N >> V;
for (int i = 1; i <= N; i++) {
cin >> v[i] >> w[i];
}
dfs(1);
cout << res << endl;
return 0;
}
果不其然，$TLE$ 了。下面使用动态规范的方法。
动态规划
状态表示和 $01$ 背包问题相同，$f[i,j]$ 表示前 $i$ 个物品，不超过体积 $j$ 的最大值。但状态计算发生了改变。
$$
f[i,j]=max(f[i,j-k*v_i]+k*w_i)\\
\{k|k*v_i<j,k\in N^+\}
$$
```cpp
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int M = 1010;
int N, V;
int v[M], w[M];
int f[M][M];
int main() {
cin >> N >> V;
for (int i = 1; i <= N; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i-1][j];
for (int k = 0; k * v[i] <= j; k++) {
f[i][j] = max(f[i][j], f[i-1][j- k*v[i]] + k*w[i]);
}
}
}
cout << f[N][V] << endl;
return 0;
}
```
好吧又又又 $TLE$ 了！！！$y$总说过动态规划的优化大部分都是从状态转移方程本身出发，我们找一下规律
$$ f[i,j]=max(f[i-1,j],f[i-1,j-v[i]]+w[i],f[i-1,j-2*v[i]]+2*w[i])\\ f[i,j-v[i]]=max(f[i-1,j-v[i]],f[i-1,j-2*v[i]]+2*w[i])\\ f[i,j]=max(f[i-1,j], f[i,j-v[i]]+w[i]) $$
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
f[i][j] = f[i-1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j- v[i]] + w[i]);
//注意这里是第 i 项的状态，区别于01背包第 i-1 项的状态
}
}
同样的我们可以按照 $01$ 背包优化的方式，进行降维操作。
for (int i = 1; i <= N; i++) {
for (int j = v[i]; j <= V; j++) {
// f[j] = f[j];
// if (j >= v[i])
f[j] = max(f[j], f[j- v[i]] + w[i]);
}
}
由于我们是利用第 $i$ 层的状态 $f[j-v[i]]$ 更新第 $i$ 层的状态 $f[j]$。所以我们不需要从右向左进行更新。
