01背包问题

动态规划问题概述

动态规划没有模板，不过可以有一套流程来帮助我们的思考，也就是y总口中的闫式$dp$分析法，先化整为零，再化零为整

动态规划是一种以空间换时间的算法，将经常算到的数据记录下来，下次用的时候直接查表，借此加速。记录数据一般用数据，也就是动态规划数组$f$[ ][ ]（不一定是两维，也许更多，也许更少）

我们从集合的角度思考问题，分为两个方面，状态表示和状态划分

$(1)$ 状态表示
1. 状态表示的意义，它表示了什么
2. 状态的属性，一般有三种，最大值，最小值和数量

$(2)$ 状态计算
当前状态可以怎么样用之前的状态表示，也就是当前划分为多个之前的状态，划分完之后，写出状态转移方程。

状态划分的时候，一定不能存在遗漏，有时候可以重复

本题思路分析

状态表示：

$f[i][j]$表示只用前$i$个装容量为$j$的背包的价值，属性是最大值

状态划分：

当前状态可以分为，不选当前物品，$f[i][j]$ = $f[i - 1][j]$和选当前物品，$f[i][j] = f[i - 1][j - v[i]] + w[i]$

我们得到的状态转移方程
$f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])$

滚动数组优化

我们可以发现，每一次状态计算我们只需要知道上一次的状态，所以可以用滚动数组进行优化，因为计算用的是上一次状态。每次计算当前状态，需要只要之前的($j$比当前$j$)小。所以我们枚举的时候要进行倒叙枚举。

如果计算时候用的本次的状态，那么正序枚举即可

不带优化的代码

for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= m; j ++ )
        f[i][j] = max(f[i - 1][j], f[i - 1][j - 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]);

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010; // 一千个物品

int n, m;
int v[N], w[N]; // v[ ]存储体积，w[ ]表示权重，也就是价格
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 ++ ) // 优化后的维dp
        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;
}