---

dp专题12 多重背包问题的二进制优化

原创 已于 2024-01-16 15:00:39 修改 · 粉丝可见 · 524 阅读 · 9 · 7 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135606101

本题链接： 5. 多重背包问题 II - AcWing题库

题目：

样例：

cobol<br/>4 5<br/>1 2 3<br/>2 4 1<br/>3 4 3<br/>4 5 2<br/>

10

思路：

对于朴素版的多重背包问题DP，由于朴素版的多重背包问题DP是三层循环，所以合适范围数据范围是在100左右，当数据范围再多 一个 10倍的时候，朴素版的多重背包问题就会 TLE 了。

朴素版的多重背包问题，原理的三层循环中，有一层循环是作为取多少个当前这个物品的原理，达到完成dp状态的转移。

我们二进制优化这个朴素版的多重背包问题，就是优化掉我们 取多少个当前这个物品 的这一层循环。

至于为什么要用二进制来优化呢？

这是因为，我们取物品的时候，就有取这个物品，和不取两种操作，其中 核心在于取多少个为合适， 二进制中各位是由  1248... 巧妙的分成了多个部分，每一部分的组合就可以到达我们预期。

比如：

目标取 的个数	各位组合
1	1
2	2
3	1 + 2
4	4
5	1 + 4
6	2 + 4
7	1 + 2 + 4

所以我们可以将物品的数量分成二进制位的组合作为新一个物品。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
// 物品结构体
struct Goods
{
	// v 作为物品体积
	// w 作为物品价值
	int v,w;
	inline Goods(int a,int b):v{a},w(b){}		
};
 
inline void solve()
{
	vector<Goods>goods;	// 存储物品
	int n,m,v,w,s;
	cin >> n >> m;
	for(int i = 1;i <= n;++i)
	{
		cin >> v >> w >> s;
		
		// 将 数量 c 分解组合 为 二进制位数的大小 的价值和容量
		for(int j = 1;s >= j;j<<=1)
		{
			s -= j;
			goods.emplace_back(Goods(v*j,w*j));	// 存储好每个组合的物品
		}
		// 如果按二进制各位的分解到最后，分解不了更高位后
		if(s > 0) goods.emplace_back(Goods(v*s,w*s)); // 就再次存储好我们剩余的数量组合
	}
	
	vector<int>dp(m + 1,0);	// dp数组
	
	// 下面就是正常的 dp 取 与 不取的 01 背包dp
	for(Goods &now:goods)
	{
		// now 作为当前物品
		for(int j = m;j >= now.v;--j)
		{
			dp[j] = max(dp[j],dp[j - now.v] + now.w);
		}
	}
	cout << dp[m] << endl;
}
 
signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}

最后提交：

​​​​​​​