分组背包算法笔记

发表于 | 分类于 | 评论数：

所有物品分成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\)，得到的方案至少不会更差。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。