背包问题

01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

状态表示、状态转移方程
$f(i,j)$表示从前i个物品中选，总体积不大于j的选法的最大价值
$f(i,j)=max(f(i−1,j),f(i−1)(j−vi)+wi)$

优化代码

int n, m;// n为物体个数，m为背包总体积
int v[N], w[N];// v[]为第i个物体的体积，w[]为第i个物体的价值
int f[N];// 记录总价值

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> v[i] >> w[i];

    // 初始化需要初始f[0][0~m]均为0，由于全局数组默认为0，所以省去了初始化
    for (int i = 1; i <= n; ++ i) 
        for (int j = m; j >= v[i]; -- j)// 优化原理在于：更新f[j]时f[j - v[i]]已经被修改了，实际上为f[i][j - v[i]]了,而非f[i - 1][j - v[i]]，所以我们应该先更新后面的再更新前面的
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }

    cout << f[m] << endl;
    return 0;
}

完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

状态表示、状态转移方程
$f(i,j)$表示从前i个物品中选，总体积不大于j的选法的最大价值
$f(i,j)=max(f(i−1)(j−k∗vi)+k∗wi)(0≤k≤j/vi)$

优化代码

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 = v[i]; j <= m; ++ j) // 注意和01背包的区别
            f[j] = max(f[j], f[j - v[i]] + w[i]);// 需要注意的是: j的遍历顺序是从小到大的，因为更新f[i][j]的是f[i][j - v],而非01背包中的f[i - 1][j - v]，也就是我们需要的f[j - v]是这一层已经更新过的，而非上一层的

    cout << f[m] << endl;

    return 0;
}

多重背包

有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

状态表示、状态转移方程
$f(i,j)$表示从前i个物品中选，总体积不大于j的选法的最大价值
$f(i,j)=max(f(i−1)(j−k∗vi)+k∗wi)(0≤k≤min(si,j/vi))$

朴素代码

int n, m;
int v[N], w[N], s[N];// s[]为第i个物品的个数
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j <= m; ++ j)
            for (int k = 0; k <= s[i] && 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][m] << endl;
    return 0;
}

分组背包

有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。

状态表示、状态转移方程
$f(i,j)$表示从前i组物品中选，总体积不大于j的选法的最大价值
$f(i,j)=max(f(i−1)(j−v[i][k])+w[i][k])(0≤k≤s[i])$
上式中v[i][k]表示第i组第k个物品的体积，w表示相同物品的价值
在第i组中的物品中任意选择一个(也可能不选)，找到其中的最大价值

优化代码

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; ++ j)
            cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; ++ i)
        for (int j = m; j >= 0; -- j) // 注意这里的顺序——类似于01背包问题的优化
            for (int k = 0; k <= s[i]; ++ k) // 考虑选择第i组中的哪个物品
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}

线性DP

数字三角形模型

最长上升子序列

状态表示、计算
$f[i]$表示的是以$a[i]$为终点的上升序列的最大值

核心代码

char a[N];
int f[N];

for (int i = 1; i <= n; i ++ )          
{
    f[i] = 1;  // 初始化f[i]为1
    for (int j = 1; j < i; j ++ )          // 状态计算（考虑前i-1个元素）
        if (a[j] < a[i])                   // 转移条件（升序条件）
            f[i] = max(f[i], f[j] + 1);    // 状态转移
}

int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

最长公共子序列

状态表示、计算
$f[i][j]$表示的是以$a[i],b[j]$为终点的公共子序列的最大值

核心代码

char a[N], b[N];
int f[N][N];

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
        else f[i][j]=max(f[i-1][j],f[i][j-1]);
    }

printf("%d\n", f[n][m]);

区间DP

状态表示、计算
$f[i][j]$表示区间 i 到 j 的方案的值

区间dp常用模板

for (int i = 1; i <= n; i++)
    f[i][i] = 初始值

for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++)   //枚举起点
    { 
        int j = i + len - 1;                 //区间终点
        for (int k = i; k < j; k++)          //枚举分割点，构造状态转移方程
            f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + w[i][j]);//状态计算
    }

计数类DP

状态表示：
$f[i][j]$表示只从1~i中选，且总和等于j的方案数
状态转移方程:
$f[i][j] = f[i - 1][j] + f[i][j - i];$

+完全背包解法

树形DP

状态表示：
$f[u][0]$：所有以u为根的子树中选择，并且不选u这个点的方案
$f[u][1]$：所有以u为根的子树中选择，并且选u这个点的方案

记忆化搜索

状态压缩DP

棋盘式状压——蒙德里安的梦想
集合式妆压——最短Hamilton路径