宝物筛选（C++，多重背包）

题目描述

终于破解了千年的难题。小 FF 找到了王室的宝物室里面堆满了无数价值连城的宝物。

这下小 FF 可发财了嘎嘎。但是这里的宝物实在是太多了小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值之后开始了宝物筛选工作小 FF 有一个最大载重为 $W$ 的采集车洞穴里总共有 $n$ 种宝物每种宝物的价值为 $v_i$重量为 $w_i$每种宝物有 $m_i$ 件。小 FF 希望在采集车不超载的前提下选择一些宝物装进采集车使得它们的价值和最大。

输入格式

第一行为一个整数 $n$ 和 $W$分别表示宝物种数和采集车的最大载重。

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。

输出格式

输出仅一个整数表示在采集车不超载的情况下收集的宝物的最大价值。

样例 #1

样例输入 #1

4 20
3 9 3
5 9 1
9 4 2
8 1 3

样例输出 #1

47

提示

对于 $30\%$ 的数据$n\le \sum m_i\le 10^4$$0\le W\le 10^3$。

对于 $100\%$ 的数据$n\le \sum m_i\le 10^5$$0\le W\le 4\times 10^4$$1\le n\le 100$。

解题思路

典型的多重背包问题

采用二进制拆分然后套用01背包动态规划即可

本来说到这里就打算结束了但感觉太水了就再说点二进制拆分

接下来简单说明一下二进制拆分

尝试将一个物品拆分为1、2、4、8…份拆分后的物品看作一个物品

如果最后一次不满足拆分条件但是仍然有剩余那么剩余的部分看作一个物品

比如说有8个物品拆分为1、2、4、1

思路很好理解吧但是与常规的二进制还是有一点不同的所以容易让人迷惑

让人迷惑通常是反正这是我感到迷惑的 为什么这样的二进制拆分与拆分之前是等价的

以有10个物品为例拆分为1、2、4、3

考虑到01背包的动态规划会尝试每一种可能的组合

也就是说只要1、2、4、3能够表示0~10的每一个数字拆分前后就是等价的

可以自行尝试一下1、2、4、3确实能够表示0~10之间的任意一个数字但这并不是巧合

1对于刚好被拆分的数字如15

15能够拆分为1、2、4、8不必证明1、2、4、8一定能够表示0~15之间的任意一个数字

2而对于不能被刚好拆分的数字$n$来说如$n\in [8,14]$

最后一次拆分出的物品一定在$[1,7]$范围内

而前三次拆分出的物品一定可以表示出$[0,7]$之内的任意一个数字

已经可以看出来了吧把最后一次拆分出的数字当作简单的偏移量即可

那么二进制拆分就说明完啦AC代码如下

//多重背包
#include <iostream>
using namespace std;
const int max_sum_m = 1e5;
const int max_n = 100;
const int max_W = 4e4;

struct treasure { int v, w, m; }t_arr[max_n + 1];//拆分前
struct treasure bin_t_arr[max_sum_m + 1];//拆分后
long long dp[max_W + 1];//滚动数组

//二进制拆分
int bin_disassembly(int n) {
	int index = 1;
	for (int i = 1; i <= n; i++) {
		int power = 1;
		while (t_arr[i].m) {
			bin_t_arr[index].m = 1;
			bin_t_arr[index].v = t_arr[i].v * power;
			bin_t_arr[index].w = t_arr[i].w * power;
			t_arr[i].m -= power;
			power *= 2; index++;
			if (t_arr[i].m < power) {
				bin_t_arr[index].m = 1;
				bin_t_arr[index].v = t_arr[i].v * t_arr[i].m;
				bin_t_arr[index].w = t_arr[i].w * t_arr[i].m;
				index++;
				break;
			}
		}
	}
	return index;//返回物品数量
}

int main() {
	int n, W, v, w, m;
	cin >> n >> W;
	for (int i = 1; i <= n; i++) {
		cin >> t_arr[i].v >> t_arr[i].w >> t_arr[i].m;
	}
	int ret = bin_disassembly(n);
	for (int i = 1; i < ret; i++) {//动态规划
		for (int j = W; j >= bin_t_arr[i].w; j--) {
			dp[j] = max(dp[j], dp[j - bin_t_arr[i].w] + bin_t_arr[i].v);
		}
	}
	cout << dp[W] << endl;
	return 0;
}