【算法】DP 之背包 — Nt_Yester

前言

欢迎各位纠错

正文

背包问题，作为 DP 经典问题，也是 OIer 必须掌握的一门算法，一般有 01 背包，完全背包，多重背包。

01 背包

01 背包是背包中最简单也是最基础的，一般用 $w_i$ 表示第 $i$ 个物品的价值，$v_i$ 表示第 $i$ 个物品的体积，而 $f_{i,j}$ 表示放 $i$ 个物品时，容量为 $j$ 的背包所能达到的最大值，进而可以推出状态转移方程：$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})$。

然后就需要用到 DP 的常用操作，滚动数组优化，来看一段话：

由于对 $f_i$ 有影响的只有 $f_{i-1}$，可以去掉第一维，直接用 $f_j$ 来表示处理到当前物品时背包容量为 $i$ 的最大价值（by OI Wiki）。

所以状态转移方程就优化成了：$f_j=\max(f_j,f_{j-w_i}+v_i)$，又因为影响 $f_i$ 的只有 $f_{i-1}$，所以内循环要反过来。

附上 P1060 的代码：

#include <iostream>

using namespace std;
int n,m,v[1001],w[1001];
int dp[300001];

int main() {
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        cin>>v[i]>>w[i], w[i] *= v[i];
    }
    for (int i=1;i<=m;i++) {
        for (int j=n;j>=v[i];j--) {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[n];

完全背包

完全背包为 01 背包的变式，其变化在于，01 背包中每个物品只能拿一次，完全背包可以无限地拿，其他定义均可以参照 01 背包。

所以其状态转移方程为 $f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)$（还有一个原始方程，但我太弱了推不出来）。

按照 01 背包的优化方式可优化为 $f_j=\max(f_j,f_{j-w_i}+v_i)$，是不是一脸懵，这不是 01 背包的吗，但别忘了，01 背包的内循环是反的（因为要保证前面没有被拿过），而完全背包可以拿无限次所以要付出最小的代价，所以，要从前往后推，也就是内循环正过来。

附上 P1616 代码：

#include<iostream>
#include<cstdio>  

using namespace std;
long long n,m,w[10011],c[10011],dp[10000010];

int main(){
    scanf("%lld%lld",&m,&n);
    for (int i=1;i<=n;i++) {
        scanf("%lld%lld",&w[i],&c[i]);
    }
    for (int i=1;i<=n;i++) {
        for (int j=w[i];j<=m;j++) {
            dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        }
    }
    printf("%lld",dp[m]);
}

多重背包

先来看一句话：

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 $k$ 个，而非一个。一个很朴素的想法就是：把「每种物品选 $k$ 次」等价转换为「有 $k$ 个相同的物品，每个物品选一次」（by OI Wiki）。

所以其状态转移方程为：$\max \limits^{k_i}_ {k=0}(f_{i-1,j-k \times w_j}+v_i \times k_i) $，时间复杂度为 $O(W\sum_{i=1}^nk_i)$。

$finally$

背包的做法还有很多，但由于篇幅限制，我就不一一放出来了。