分组背包算法笔记

所有物品分成K类,每类最多只能选择一件物品的背包问题。

\(N\) 件物品和一个容量为 \(V\) 的背包。第 \(i\) 件物品的重量是 \(C_i\),价值是 \(W_i\)。这些物品被划分为\(K​\)组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设\(F [k, v]\)表示前\(k\)组物品花费费用\(v\)能取得的最大权值,则有: \[ F[k, v]=\max \left\{F[k-1, v], F\left[k-1, v-C_{i}\right]+W_{i} \mid \text { item } i \in \operatorname{group} k\right\} \] 使用一维数组的伪代码是:

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
分组背包
*/
#include <bits/stdc++.h>
#pragma warning(disable:4996)
#define WindSings
using namespace std;

vector<vector<int>> weight;
vector<vector<int>> value;

void init()
{
weight.resize(4);
value.resize(4);
weight[1] = { 1,4,3,5,2 };
value[1] = { 1,5,7,9,3 };
weight[2] = { 2,3,1 };
value[2] = { 5,3,7 };
weight[3] = { 5,2,3 };
value[3] = { 4,2,2 };
}

int main()
{
init();
int K = 3; //组的数量
int C = 15; //包的容量
vector<int>dp;
dp.resize(C + 1);
for (int i = 1; i <= K; i++)
{
for (int j = C; j >= 0 ; j--)
{
for (int t = 0; t < weight[i].size(); t++)
{
if(j>= weight[i][t])
dp[j] = max(dp[j], dp[j - weight[i][t]] + value[i][t]);
}
}
}
cout << dp[C] << endl;
//输出20,选择的是第一组的(weight=5,value=9),第二组的(1,7),第三组的(5,4)
system("pause");
return 0;
}

简单优化:

若若两件物品\(i\)\(j\)满足\(W_i ≤ W_j\)\(V_i ≥ V_j\),则将可以将物品\(j\)直接去掉,不用考虑。

这个优化的正确性是显然的:任何情况下都可将价值小费用高的 \(j\) 换成物美价廉的\(i\),得到的方案至少不会更差。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。