分组背包算法原理与经典例题解析

分组背包

1. 定义

给定一个整数 m 表示背包的容量，有 n 个货物可供挑选。每个货物有自己的体积、价值、组号。同一个组的物品只能挑选一件，所有挑选物品的体积总和不能超过背包容量。

如何挑选货物能达到价值最大？返回最大价值。

2. 状态定义

dp[i][j] 表示前 i 组上，每组只能选一件商品（注意：i 表示的是组，不是商品），容量不超过 j 的条件下的最大价值。

• 不选第 i 组商品：满足条件，即 dp[i-1][j]。
• 选第 i 组商品：考虑选哪一件？全试！
  • a: dp[i-1][j-a 的体积] + a 的价值
  • b: dp[i-1][j-b 的体积] + b 的价值
  • c: dp[i-1][j-c 的体积] + c 的价值 （注意：a, b, c 是 i 组中的商品）

关键是给物品分好组，这样才能进行后面的计算。

3. 时间复杂度

for(组的数量)
    for(背包容量)
        for(组内物品数量)

组 1：m * 组 1 物品数量 组 2：m * 组 2 物品数量 …… 组 i：m * 组 i 物品数量 总复杂度：O(m * 物品总个数)

---

例题一：通天之分组背包

题目描述

自 01 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 m, n，表示一共有 n 件物品，背包能承受的最大重量为 m。 接下来 n 行，每行 3 个数 ai, bi, ci，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

示例

输入： 45 3 10 10 1 10 5 1 50 400 2

输出： 10

说明/提示

0 ≤ m ≤ 1000，1 ≤ n ≤ 1000，1 ≤ k ≤ 100，ai, bi, ci 在 int 范围内。

代码实现

#include <stdio.h>
#define MAXN 1010
#define MAXM 1010

typedef struct {
    int w;
    int v;
    int k;
} Node;

Node a[MAXN];
int dp[MAXN][MAXM]; // dp[i][j] 表示前 i 组，容量为 j 时的最大价值

int max {
     a > b ? a : b;
}

{
    
     teams = ;
     ( i = ; i <= n; i++) {
         (a[i].k != a[i].k) {
            teams++;
        }
    }
    
     start = ; 
     end = ;   
     i = ;     

    
     (start = , end = , i = ; start <= n; i++) {
        
         (end <= n && a[end].k == a[start].k) {
            end++;
        }
        
        
        
         ( j = ; j <= m; j++) {
            
            
            
            dp[i][j] = dp[i][j];
            
             ( g = start; g < end; g++) {
                 (j >= a[g].w) {
                    dp[i][j] = (dp[i][j], dp[i][j - a[g].w] + a[g].v);
                }
            }
        }
        
        start = end;      
        end++;            
    }
     dp[i][m]; 
}

{
     m, n;
    (, &m, &n);
    
     ( i = ; i <= n; i++) {
        (, &a[i].w, &a[i].v, &a[i].k);
    }
    
     ( i = ; i < n; i++) {
         ( j = ; j <= n - i; j++) {
             (a[j].k > a[j].k) {
                Node temp = a[j];
                a[j] = a[j];
                a[j] = temp;
            }
        }
    }
     sum = (m, n);
    (, sum);
     ;
}