526互联

动态规划--DP

发布时间 2023-10-05 20:59:58作者: chfychin

动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

背包

01背包

每个物体只有两种可能的状态（取与不取），对应二进制中的 \(0\) 和 \(1\)，这类问题便被称为「0-1 背包问题」。

状态转移方程：

\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i}) \]

这里如果直接采用二维数组，有多余空间浪费

由于每个物品只有选或不选两种情况，即最多选一次，故可从体积出发逆向枚举每个物品

\[for(int\ j=m;j>=v[i];j--) \]

\[f[j]=max(f[j],f[j-v]+w[i]) \]

时间复杂度：\(O(n\times v)\)

点击查看代码 
for(int i = 1; i <= n; i ++)
{
    for(int j = m; j >= v[i]; j --)
		dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}

完全背包

完全背包模型与 \(0-1\) 背包类似，与 \(0-1\) 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

虑一个朴素的做法：对于第 i 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 \(O(n^3)\) 的。

状态转移方程如下：

\[f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k) \]

考虑做一个简单的优化。可以发现，对于 \(f_{i,j}\)，只要通过 \(f_{i,j-w_i}\) 转移就可以了。因此状态转移方程为：

\[f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i) \]

时间复杂度：\(O(n\times v)\)

理由是当我们这样转

每个物品可选无数次，故可以从体积出发正向枚举每个合法的物品

\[for(int\ j=1;j<=m;j++) \]

\[f[j]=max(f[j],f[j-v]+w[i]) \]

点击查看代码 
for(int i = 1; i <= n; i ++)
{
    for(int j = v[i]; j <= m; j ++)
		dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}

多重背包

多重背包也是 \(0-1\) 背包的一个变式。与 \(0-1\) 背包的区别在于每种物品有 \(k_i\) 个，而非一个。

一个很朴素的想法就是：把「每种物品选 \(k_i\) 次」等价转换为「有 \(k_i\) 个相同的物品，每个物品选一次」。这样就转换成了一个 \(0-1\) 背包模型，套用上文所述的方法就可已解决。状态转移方程如下：

\[f_{i,j}=\max_{k=0}^{k_i}(f_{i-1,j-k\times w_i}+v_i\times k) \]

时间复杂度 \(O(W\sum_{i=1}^nk_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]] + w[i] * k);
    }
}

混合背包

混合背包就是将前面三种的背包问题混合起来，有的只能取一次，有的能取无限次，有的只能取 \(k\) 次。

按照背包种类分类求解，求最优解

例. 混合背包问题

题目描述：

有 N 种物品和一个容量是 V 的背包。

物品一共有三类：

·第一类物 品只能用\(1\)次（\(01\)背包）；
·第二类物品可以用无限次（完全背包）；
·第三类物品最多只能用 \(s_i\) 次（多重背包）；每种体积是 \(v_i\)，价值是 \(w_i\)。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式：

第一行两个整数，\(N，V\)，用空格隔开，分别表示物品种数和背包容积。

接下来有 \(N\) 行，每行三个整数 \(v_i,w_i,s_i\)，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

·\(s_i=−1\) 表示第 \(i\) 种物品只能用1次；
·\(s_i=0\) 表示第 \(i\) 种物品可以用无限次；
·\(s_i>0\) 表示第 \(i\) 种物品可以使用 \(s_i\)次；

输出格式：

输出一个整数，表示最大价值。

输入

4 5
1 2 -1
2 4 1
3 4 0
4 5 2

输出

8

点击查看代码 
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 1e3 + 10;

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

void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        cin >> w[i] >> v[i] >> s[i];
        if(!s[i])
            for(int j = w[i]; j <= m; j ++)
                f[j] = max(f[j], f[j - w[i]] + v[i]);
        else
        {
            if(s[i] == -1) s[i] = 1;
            for(int k = 1; k <= s[i]; k *= 2)
            {
                for(int j = m; j >= k * w[i]; j --)
                    f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);
                s[i] -= k;
            }
                
            if(s[i])
                for(int j = m; j >= s[i] * w[i]; j --)
                f[j] = max(f[j], f[j - s[i] * w[i]] + s[i] * v[i]);
        }
    }
    cout << f[m] << endl;
}

signed main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

二进制优化

具体地说就是令 \(A_{i,j}\left(j\in\left[0,\lfloor \log_2(k_i+1)\rfloor-1\right]\right)\) 分别表示由 \(2^{j}\) 个单个物品「捆绑」而成的大物品。特殊地，若 \(k_i+1\) 不是 \(2\) 的整数次幂，则需要在最后添加一个由 \(k_i-2^{\lfloor \log_2(k_i+1)\rfloor-1}\) 个单个物品「捆绑」而成的大物品用于补足。

将每种物品按照上述方式拆分后，使用 0-1 背包的方法解决即可。

时间复杂度: \(O(W\sum_{i=1}^n\log_2k_i)\)

点击查看代码 
for(int i = 1; i <= n; i ++)
	{
		cin >> w >> v >> s;
		int k = 1;
		while(s > k)
		{
			s -= k;
			p[cnt ++] = {w * k, v * k};
			k *= 2;
		}
		p[cnt ++] = {w * s, v * s};
	}
	for(int i = 0; i < cnt; i ++)
		for(int j = m; j >= p[i].w; j --)
			f[j] = max(f[j], f[j - p[i].w] + p[i].v);

单调队列优化

点击查看代码 
for(int i = 1; i <= n; i ++)
    {
        for(int r = 0; r < v[i]; r ++)
        {
            int hh = 0, tt = -1;
            for(int j = r; j <= m; j += v[i])
            {
                while(hh <= tt&&j - q[hh] > v[i] * s[i]) hh ++;
                while(hh <= tt&&f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) tt --;
                q[++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }

二维费用背包

和 \(0-1\) 背包问题类似，不同的是选一个物品会消耗两种价值（经费、时间），可对每种价值进行\(0-1\)背包

点击查看代码 
for(int i = 0; i < n; i ++)
{
    for(int j = V; j >= v[i]; j --)
    {
        for(int l = W; l >= w[i]; l --)
            f[j][l] = max(f[j][l], f[j - v[i]][l - w[i]] + a[i]);
    }
}

分组背包

从「在所有物品中选择一件」变成了「从当前组中选择一件」，可对每一组进行一次 \(0-1\) 背包。

点击查看代码 
for(int i = 1; i <= n; i ++)
{
    for(int j = m; j >= 0; j --)
    {
        for(int  k = 1; k <= s[i]; k ++)
            if(j >= v[i][k])
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    }
}

有依赖的背包

考虑分类讨论。对于一个主件和它的若干附件，有以下几种可能：只买主件，买主件 + 某些附件。因为这几种可能性只能选一种，所以可以将这看成分组背包。

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合。

有依赖的背包问题

题目描述：

有 \(N\) 个物品和一个容量是 \(V\) 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 \(i\)，体积是 \(v_i\)，价值是 \(w_i\)，依赖的父节点编号是 \(p_i\)。物品的下标范围是 \(1…N\)。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式：

第一行有两个整数 \(N，V\)，用空格隔开，分别表示物品个数和背包容量。

接下来有 \(N\) 行数据，每行数据表示一个物品。第 \(i\) 行有三个整数 \(v_i,w_i,p_i\)，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 \(p_i=−1\)，表示根节点。 数据保证所有物品构成一棵树。

输出格式:

输出一个整数，表示最大价值。

输入

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出

11

点击查看代码 
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long

using namespace std;

const int N = 110;
vector<int> g[N];
int f[N][N];
int v[N], w[N];
int n, m, root;

void dfs(int x)
{
    for(int i = v[x]; i <= m; i ++)
        f[x][i] = w[x];
    for(int i = 0; i < g[x].size(); i ++)
    {
        int y = g[x][i];
        dfs(y);
        for(int j = m; j >= v[x]; j --)
        {
            for(int k = 0; k <= j - v[x]; k ++)
                f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int fa;
        cin >> v[i] >> w[i] >> fa;
        if(fa == -1) root = i;
        else
            g[fa].push_back(i);
    }
    dfs(root);
    cout << f[root][m] << "\n";
}
signed main()
{
    IOS;
    int _ = 1;
    // cin >> _;
    while(_ --)
        solve();
    return _ ^ _;
}

泛化物品的背包

这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为 \(V\) 的背包问题中，当分配给它的费用为 \(v_i\) 时，能得到的价值就是 \(h\left(v_i\right)\)。这时，将固定的价值换成函数的引用即可。

杂项

根据贪心原理，当费用相同时，只需保留价值最高的；当价值一定时，只需保留费用最低的；当有两件物品 \(i,j\) 且 \(i\) 的价值大于 \(j\) 的价值并且 \(i\) 的费用小于 \(j\) 的费用时，只需保留 \(i\)。

背包问题变种

输出方案其实就是记录下来背包中的某一个状态是怎么推出来的。我们可以用 \(g_{i,v}\) 表示第 \(i\) 件物品占用空间为 \(v\) 的时候是否选择了此物品。然后在转移时记录是选用了哪一种策略（选或不选）。

求方案数

对于给定的一个背包容量、物品费用、其他关系等的问题，求装到一定容量的方案总数。

这种问题就是把求最大值换成求和即可。

例如 \(0-1\) 背包问题的转移方程就变成了：

\[\mathit{dp}_i=\sum(\mathit{dp}_i,\mathit{dp}_{i-c_i}) \]

初始条件：\(\mathit{dp}_0=1\)

因为当容量为 \(0\) 时也有一个方案，即什么都不装。