算法【分组背包】

分组背包是指多个物品分组，每组只能取1件。每一组的物品都可能性展开就可以了。注意时间复杂度不会升阶，O(物品数量 * 背包容量)。

下面通过题目加深理解。

题目一

测试链接：通天之分组背包 - 洛谷

分析：这道题是分组背包的模板，对每个分组进行可能性的展开即不取这个分组和取这个分组的每一个能取的物品。下面代码采用记忆化搜索，严格位置依赖和空间压缩的解法不再赘述。代码如下。

#include <iostream>
#include <vector>
using namespace std;
int m, n;
int number_of_group = 0;
vector<vector<int>> group;
int data[1000][2];
int dp[100][1001];
int f(int groups, int weight){
    if(groups == number_of_group){
        return 0;
    }
    if(dp[groups][weight] != -1){
        return dp[groups][weight];
    }
    int ans = f(groups+1, weight);
    int nums = group[groups].size();
    for(int i = 0;i < nums;++i){
        if(weight - data[group[groups][i]][0] >= 0){
            ans = ans > f(groups+1, weight - data[group[groups][i]][0]) + data[group[groups][i]][1] ?
            ans : f(groups+1, weight - data[group[groups][i]][0]) + data[group[groups][i]][1];
        }
    }
    dp[groups][weight] = ans;
    return ans;
}
int main(void){
    int a_i, b_i, c_i;
    scanf("%d%d", &m, &n);
    vector<int> temp;
    for(int i = 0;i <= 99;++i){
        group.push_back(temp);
    }
    for(int i = 0;i < n;++i){
        scanf("%d%d%d", &a_i, &b_i, &c_i);
        data[i][0] = a_i;
        data[i][1] = b_i;
        group[c_i].push_back(i);
        number_of_group = number_of_group > c_i ?
        number_of_group : c_i;
    }
    ++number_of_group;
    for(int i = 0;i <= number_of_group-1;++i){
        for(int j = 0;j <= m;++j){
            dp[i][j] = -1;
        }
    }
    printf("%d", f(0, m));
    return 0;
}

其中，f函数返回在从组数为groups的组开始，剩余重量为weight的情况下的最大值。

题目二

测试链接：2218. 从栈中取出 K 个硬币的最大面值和 - 力扣（LeetCode）

分析：对于这道题，可以将每个栈看为一个分组，对每个分组进行可能性的展开，也就是不取这个栈和取1次、2次、3次......直到剩余次数和栈的硬币数的最小值。代码采用记忆化搜索，改成严格位置依赖和空间压缩的解法不再赘述。代码如下。

class Solution {
public:
    int dp[1000][2001];
    int f(int index, int times, vector<vector<int>>& piles){
        if(index == piles.size()){
            return 0;
        }
        if(dp[index][times] != -1){
            return dp[index][times];
        }
        int ans = f(index+1, times, piles);
        int length = piles[index].size();
        int sum = 0;
        for(int i = 0;i < length && i+1 <= times;++i){
            sum += piles[index][i];
            ans = ans > f(index+1, times-i-1, piles) + sum ?
            ans : f(index+1, times-i-1, piles) + sum;
        }
        dp[index][times] = ans;
        return ans;
    }
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        for(int i = 0;i < 1000;++i){
            for(int j = 0;j < 2001;++j){
                dp[i][j] = -1;
            }
        }
        return f(0, k, piles);
    }
};

其中，f方法返回在从下标index的栈开始取，剩余次数为times的情况下，得到的最大值。