多重背包问题 — 朴素做法
同样用闫氏dp分析法分析
|集合 : 从1 ~ i 个物品中选,且总体积不超过j的集合 (这里与 01背包问题和完全背包问题集合相同)
|
|
|----------状态表示--------|
| |
| |
| |属性 : 集合中所有可行方案中价值的最大值 max
DP
|
|
|
|
|----------状态计算 : 根据集合划分,将一个大集合划分为若干个子集,
设我们要求解f(i,j), 然后来尝试将其分为更小的集合
个人喜欢的是喜欢先二分, 二分为(1) 不包含第i个物品的集合 (2) 包含第 i 个物品的集合
(1) 情况是由前面推导的故直接为 f(i - 1, j);
(2) 情况需要继续细分集合, 分为包含第i个物品1,2, 3, 4, .... , k个的情况.
故这里可以直接有下面的朴素做法, 三层for循环 ,时间复杂度为 nmk, k不固定。
#include<iostream>
using namespace std;
constexpr int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
auto main() -> int
{
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> s[i];
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
f[i][j] = f[i - 1][j];
for(int k = 1; k <= s[i] && k * v[i] <= j; ++k)
f[i][j] = max(f[i][j], f[i - 1][j - k*v[i]] + k * w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
但由于其时间复杂度为 nmk, 很大,故当数据很大的时候会TLE, 例如在多重背包问题 II这个问题中这段代码就通不过,因为其最大的数据量
有40亿, 而 C++ 每一秒大概处理的数据为 1 亿。
多重背包优化 ----> 二进制优化
这里引入一个概念叫打包, 例如此时的第i个物品的个数为 1023, 则我们如果按照上面的写法就是从 1 ~ 1023遍历一遍,但如果我们将其分为10组
那么我们就只要遍历10次即可,具体如何分析,看下面:
我们将第i个物品的个数为 1023, 分为10组
第一组 (1) 1 , 包含一个第i个物品 第二组 (2) 2, 包含两个第i个物品, 第三组(3) 包含4个第i个物品, 第四组 (4) 包含8个第i个物品
直到 第10组 (10)包含 512 个第i个物品。 这样的十组我们发现其包含的个数恰好是2的整数次方, 例如想表示第i个物品选了3个的情况,那么就
是第(1),(2) 组都选了所在组的第i个物品的情况, 再比如想表示第i个物品全选了的情况就是这十组都选了各自组所有i的情况,这样对于每一组就是
一个01背包问题, 这里的情况1023恰好是能被分为10组的情况,如果是其他情况,例如200. 这时同样根据前面的分组 : (1) 1. (2) 2, (3) 4, (4) 8
(5) 16, (6) 32, (7) 64, 此时第8组不能写 128, 不然总共超过了200了, 故第 8 组为 (8) 73 ;
故从这里知道分组规律: 1, 2, ...., 2 ^ k, c; (c < 2 ^ (k + 1)), 故常数c前面表示的一个范围为 [0, 2 ^ (k+1) - 1], 加上常数c其表示的范围为 [c ~ s];
s为第i个物品的总数, 故这两个区间有没有可能存在不连续的问题呢,答案是否的,因为前面已经知道了c < 2 ^ (k + 1), 而且这里只能取整数,故这两个区间
一定是连续的。 故这种写法我们的时间复杂度为nmlogs 代码如下:
#include<iostream>
using namespace std;
constexpr int N = 12 * 1100; // 由于这里将第i个物品的个数进行分组,分组的个数为 log2(s),其中s为第i个物品的个数, 然后物品的种类最大为 1000, 每个物品的数量最多为2000, log2(2000) --> 上取整 11 + 1
int n, m;
int v[N], w[N];
int f[N]; // 这里直接优化空间,这里不优化的话,空间会不够
auto main() -> int
{
cin >> n >> m;
int cnt = 0;
for(int i = 1; i <= n; ++i) // 进行分组
{
int a, b, c; cin >> a >> b >> c;
int k = 1;
while(k <= c)
{
v[++cnt] = k * a;
w[cnt] = k * b;
c -= k;
k *= 2;
}
if(c > 0) // 若c > 0 说明有剩余,单独成组
{
v[++cnt] = c * a;
w[cnt] = c * b;
}
}
n = cnt; // 更新物品的种类
for(int i = 1; i <= n; ++i) // 然后就是分好的每一组中做01背包的问题
for(int j = m; j >= v[i]; --j)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
可不可以解释一下时间复杂度nmlogs怎么来的啊?
第一个for循环是nlogs,下面的双层for循环是nm,两个时间复杂度不应该相加嘛