【C++】动态规划|背包问题模板

Toms Project • • 信息技术 • 65 阅读

背包问题应该是初学DP的人最先接触的（至少我是）。显然也存在复杂亿点点的。这里简单存一下。

01背包

求最大价值

注意内层倒序。

题目：[NOIP 2005 普及组] 采药（https://www.luogu.com.cn/problem/P1048）

C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int main()
{
	int t, m;
	cin >> t >> m;
	vector<int> status(t + 3, 0);
	vector<pair<int, int>> item(m + 1, pair<int, int>(0, 0));
	for (int i = 1; i <= m; i++) cin >> item[i].first >> item[i].second;
	for (int i = 1; i <= m; i++)
	{
		for (int j = t; j >= item[i].first; j--)
		{
			status[j] = max(status[j], status[j - item[i].first] + item[i].second);
		}
	}
	cout << status[t] << endl;
	return 0;
}

求方案数

只需修改状态转移方程为求和，注意初始化status[0]=1！！！

求可行性

完全背包

求最大价值

只需将01的倒序循环改为正序即可。

题目：疯狂的采药（https://www.luogu.com.cn/problem/P1616）

C++
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	int t, m;
	cin >> t >> m;
	vector<pair<int, int>> item(m + 1, pair<int, int>(0, 0));
	vector<long long> f(t + 3, 0);
	for (int i = 1; i <= m; i++)
	{
		cin >> item[i].first >> item[i].second;
	}
	for (int i = 1; i <= m; i++)
	{
		for (int j = item[i].first; j <= t; j++)
		{
			f[j] = max(f[j], f[j - item[i].first] + item[i].second);
		}
	}
	cout << f[t] << endl;
	return 0;
}

求方案数

同01背包，只需修改状态转移方程为求和，注意初始化f[0]=1！！！

多重背包

常规算法(求最大价值)

在01的基础上加入一层循环枚举物品数量。

由于是三层循环，时间复杂度来到了O(n^3)

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> f(m + 3);
	vector<vector<int>> item(n + 1, vector<int>(3, 0));
	for (int i = 1; i <= n; i++) cin >> item[i][0] >> item[i][1] >> item[i][2];
	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= item[i][0]; j--)
		{
			for (int k = 0; k <= item[i][2]; k++)
			{
				if (j < k * item[i][0]) break;
				f[j] = max(f[j], f[j - k * item[i][0]] + k * item[i][1]);
			}
		}
	}
	cout << f[m] << endl;
	return 0;
}

二进制优化

利用数字被拆分为1，2，4，8...的性质，压缩物品，弱化为01背包问题。

可以把时间复杂度降到O(n^2log n).

题目：[NOI 导刊] 宝物筛选（https://www.luogu.com.cn/problem/P1776）

C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int main()
{
	int n, w, vv, ww, mm;
	vector<pair<int, int>> item;
	cin >> n >> w;
	vector<int> f(w + 3);
	for (int i = 0; i < n; i++)
	{
		cin >> vv >> ww >> mm;
		for (int j = 1; j <= mm; j <<= 1)
		{
			item.emplace_back(make_pair(vv * j, ww * j));
			mm -= j;
		}
		if (mm)
		{
			item.emplace_back(make_pair(vv * mm, ww * mm));
		}
	}
	for (int i = 0; i < item.size(); i++)
	{
		for (int j = w; j >= item[i].second; j--)
		{
			f[j] = max(f[j], f[j - item[i].second] + item[i].first);
		}
	}
	cout << f[w] << endl;
	return 0;
}

单调队列优化

需要正序处理。为防止结果被覆盖，所以需要保存f中当前结果到ff。利用单调队列维护一个滑动窗口，维护单位内的最优结果。

最优情况下时间复杂度可以压到O(n^2)，但是常数小，这种情况很罕见。

题目：[NOI 导刊] 宝物筛选（https://www.luogu.com.cn/problem/P1776）

C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int main()
{
	int n, t;
	cin >> n >> t;
	vector<int> v(n), w(n), m(n), f(t + 3);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i] >> w[i] >> m[i];
	}
	for (int i = 0; i < n; i++)
	{
		auto ff = f;
		for (int j = 0; j < w[i]; j++)
		{
			deque<int> q;
			for (int k = j; k <= t; k += w[i])
			{
				if (!q.empty() && q.front() < k - m[i] * w[i]) q.pop_front();
				if (!q.empty()) f[k] = max(ff[k], ff[q.front()] + (k - q.front()) / w[i] * v[i]);
				while (!q.empty() && ff[k] >= ff[q.back()] + (k - q.back()) / w[i] * v[i]) q.pop_back();
				q.emplace_back(k);
			}
		}
	}
	cout << f[t] << endl;
	return 0;
}

求方案数

和前面同理，只需修改状态转移方程为求和，注意初始化f[0]=1！！！

题目：[NOIP 2012 普及组] 摆花（https://www.luogu.com.cn/problem/P1077）

C++
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> item(n, 0), f(m + 3);
	f[0] = 1;
	for (int i = 0; i < n; i++) cin >> item[i];
	for (int i = 0; i < n; i++)
	{
		for (int j = m; j >= 1; j--)
		{
			for (int k = 1; k <= item[i]; k++)
			{
				if (j < k) break;
				f[j] = (f[j] + f[j - k]) % 1000007;
			}
		}
	}
	cout << f[m] % 1000007 << endl;
	return 0;
}

二维/多维费用背包

就是原来只有一种条件（背包的容量），现在有了两个甚至是多个限制条件。可以通过给每个条件都加入一层循环来尝试即可。

其他

这里主要是作者遇到的其他特殊类型的，但是又属于背包类动态规划问题的一些内容/题目。

交换条件

比较新奇的一种思路。存在一种情况，即背包容量特别大而最大价值有限，这时候居然可以把二者交换一下。。。

此时把题目中的物品的总价值视为背包的容量，限制条件视为价值，在跑对应的背包。

一定一定一定注意最后输出的时候要换回来....

题目：[天梯赛模拟] 拼题A打卡奖励（垃圾PTA甚至看题还要收费....那我就要把题目免费放出来了）

一眼就可以发现这是01背包，但是细细观察，发现M太大了（其实是自信一发TLE），这时候按照前面提到了思路，反一下容量与价值，再按01模板来算即可。

C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, coin = 0;
	cin >> n >> m;
	vector<pair<int, int>> item(n);
	for (auto& i : item) cin >> i.first;
	for (auto& i : item)
	{
		cin >> i.second;
		coin += i.second;
	}
	vector<int> f(coin + 5, 0xfffff);
	f[0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = coin; j >= item[i].second; j--)
		{
			f[j] = min(f[j], f[j - item[i].second] + item[i].first);
		}
	}
	for (int i = coin; i >= 0; i--)
	{
		if (f[i] <= m)
		{
			cout << i << endl;
			break;
		}
	}
	return 0;
}

好了。感觉我知道的背包类动态规划就这么多了。如果再有还是会补充的。

希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。

版权声明：
作者：Toms Project
链接：https://blog.projectoms.com/pages/1540.html
来源：Toms Project 官方博客
文章版权归作者所有，未经允许请勿转载。

THE END
分享
二维码
打赏
< <上一篇
下一篇>>
文章目录
关闭
目 录