01背包问题

背包问题笔记

标签（空格分隔）： dp 背包学习中的一些疑问解决

1. 1_01背包问题

1.1暴力搜索写法：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int inf = -(1e9 + 10);
int n, m;
int f[maxn][maxn];
int v[maxn], w[maxn];
int dfs(int now, int have) //分别表示第几个，以及现在的背包重量是多少。
{
    if (have > m)
        return inf;
    if (now > n)
        return 0;
    return max(dfs(now + 1, have), dfs(now + 1, have + w[now]) + v[now]);  
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];、
    cout<<dfs(1,0)<<'\n';
    
}

1.11回顾tips

dfs函数的意义是，当前状态之后的最优状态。也可以理解为子问题：（背包已经使用容量have，从第now个物件开始选择的最优解。）该问题的解。
可以看到，该问题的解是和其他状态相关的。

1.2记忆化搜素写法：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int inf = -(1e9 + 10);
int n, m;
int f[maxn][maxn];
int v[maxn], w[maxn];
int dfs(int now, int have) //分别表示第几个，以及现在的背包重量是多少。
{
    if (have > m)
        return inf;
    if (now > n)
        return 0;
    if (f[now][have] > 0)
        return f[now][have];
    return f[now][have] = max(dfs(now + 1, have), dfs(now + 1, have + w[now]) + v[now]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    cout << dfs(1, 0) << '\n';
}

1.21回顾tips:

相对于暴力搜索，将每一个人函数线作为一颗树的节点，发现、一整个搜索树中，有接个状态会是重复的。
将某个状态的计算结果保存，可以做到一定的优化。减少多个子树的计算。

1.3抽象出二重循环，计算各个子问题的解(正推如下)。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int w[maxn];
int v[maxn];
int f[maxn][maxn];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= w[i])
                f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
        }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = max(ans, f[n][i]);
    cout << ans << '\n';
}

详解如下
- $d_{i,j}$ 定义为问题（背包容量为j，从第1到第i个物品开始选择方案的最大价值）的解；
- 满足题意得情况下; $d_{i,j}=max(d_{i-1,j},d_{i-1,j-w_i}+v_i)$

1.4对简单二重循环的优化。（滚动数组，常数优化）

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 1003;
int f[maxn];
int v[maxn], w[maxn];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= w[i]; j--)
            f[j] = max(f[j], f[j - w[i]] + v[i]);
    cout << f[m] << '\n'; //第一个疑问点。为什么f[m]就是ans;
}

1.41回顾tips:

可以发现，在状态得转移中，就这一个表结构上有如下规律：
- 满足题意得情况下： 1 . 第i行得转移只用到了第i-1行的数据。 2 . 只要保证可以获取某个数据在i-1行中的数据，每个dp的计算是独立的。
- 做出如下改进： 1 . 发现一个特征函数转移对应的i-1行的特征函数，都是在它之前的，从后面开始第二重循环中从后往前即可。可以保证，前面的额数据也可以用到转移过程中需要的特征函数。 2 . 可以修正第二重循环的上界为 $w_{i}$ ，更前面的只能够选择 $f_{i-1,j}$ 就是相当于没有变化。
关于最后 $f_{m}$ 就是答案结论的证明。
- 最直白的理解：按照它的意义来说，我们确保了，转移后得到的数据成果，就是子问题的最优解。这样对该问题不要求严格装满的题意下： $f_m>=f_k,f_k=max\_v$ 。
- 就正推的转移方式上看
  - 假设 $f_k=max\_value$
  - 选择第一个物品后的 $f_{i}$ 的分布情况是 $0..., 0, v_{i}, v_{i} . . . .$
  - 按照转移规则，第二次选择 $f_k=>max(if(k>=w_i)f_{k-w_i},f_k)$ $f_m=>max(if(m>=w_i)f_{m-w_i},f_m)$
    相对于 $f_{m}$ 的转移对象来说， $f_{k}$ 的转移对象一直位于更前面的位置。而上一个序列的情况是是单调的，因此，经过这一次转移后， $f (x)$ 也保持了单调性。
  - 数学归纳法得到了完成转移之后， $f_{m} > = f_{k}$