# python
from typing import List

# 组内01背包 计算容量取[0,c]中任意值时的组内最大下载量并返回dp数组
def max_downloads(lists: List[list], cont: int) -> List[int]:
    n = len(lists)
    dp = [0 for _ in range(cont + 1)]
    for i in range(0, n):
        for j in range(cont, 0, -1):
            size, nums = lists[i]
            if size <= j:
                dp[j] = max(dp[j], dp[j - size] + nums)
    return dp

def main():
    graph = []
    n, m, c = map(int, input().split())
    for _ in range(n):
        lists = []
        for _ in range(m):
            lists.append(list(map(int, input().split()))[1:])
        # 组内01背包 计算各组在不同容量时的最大下载量并保存
        graph.append(max_downloads(lists, c))
    # 组间01背包 计算不同组之间在容量为[0,c]中任意值时的最大下载量
    pre = graph[0].copy()
    for i in range(1, n):
        dp = [-1 for _ in range(c + 1)]
        for j in range(1, c + 1):
            for k in range(1, j):
                # 只有在保证之前的组和当前组都有值（都取过）时才判断大小并赋值
                if pre[j - k] > 0 and graph[i][k] > 0:
                    dp[j] = max(dp[j], pre[j - k] + graph[i][k])
        # dp数组保存的是 内存属于[0,c]时 且当前组和之前组都有值（都取过）时 的最大值
        pre = dp.copy()
    print(pre[-1])


if __name__ == '__main__':
    main()

更新一下塔子哥对应的python 记忆化搜索思路。

题目大意

一个拥有一定容量的背包，有n组物品，每组物品有容量和价值。每组里至少选择一个，问能选出的最大价值。

思路

我们可以先考虑对于每一组物品，我们给他们分配多少的容量。这个问题可以分两步走:

step1:整体分配

找到一个长度为n(分组个数)的sz序列，使得这个序列的和<=c，且每个元素 >= 1。

这里$sz_i$ 是给第$i$组分配的容量大小。

step2 :单组最优解

这里容易发现，如果对一个分组，我们已经确定他的容量为$sz_i$了，那么对这一组来说，就是一个01背包模型。

回到step1:这个问题本身也是一个动态规划问题。$dp[i][j]$ 代表考虑了前i个分组，并且已经用了$j$容量的最优解。转移为:

$dp[i][j] = max(dp[i - 1][j - k] + f[i][k])$ , k枚举从1到j - 1。 $f[i][k]$代表给第i个分组分配$k$容量情况下的最优解。

样例解释

拿样例2来说，我们先对每个分组做01背包，得到的结果如下： dp_of_0 = {0,-1,-1,-1,-1,2,-1,-1,-1,-1,3}

dp_of_1 = {0,-1,-1,-1,-1,-1,2,-1,-1,-1,-1}

那么第一组的物品变成:(sz = 5 , value = 2) , (sz = 10 , value = 3)

第二组的物品变成:(sz = 6 , value = 2)

接下来我们对这些物品再做一遍01背包。但是过程中需要保证每个分组至少有一个进程被选中。

这个问题转化为：找到一个长度为n(分组个数)的sz序列，使得这个序列的和<=c，且这个序列的value和最大，且每个元素 >= 1。

对于样例2，这个序列显然找不到。因为第一组的物品的sz序列为5,10，第二组的物品的sz序列为6。min(5,10)+min(6)=11>c。

也就是说从每个分组去抽选最小sz都无法满足条件。

那么这个问题同样可以用01背包解决。我们设f[i]表示总共大小为i的时候的最大value和。 转移方程为f[i] = max(f[i],f[i-j]+dp_of_j)。其中j为第j个分组的大小。过程中需要保证j >= 1 , <= i ，因为需要保证j因为每个分组至少有一个进程被选中

代码

Python

n , m , c = map(int, input().split())
a = {}
# 读入数据
for _ in range(n):
    for _ in range(m):
        idx , sz , value = map(int, input().split())
        if idx not in a:
            a[idx] = []
        a[idx].append((sz , value))
# 先对每个分组进行01背包
dp = {}
for idx in a:
    dp[idx] = [-1] * (c + 1)
    dp[idx][0] = 0
    for sz , value in a[idx]:
        for i in range(c , sz - 1 , -1):
            if dp[idx][i - sz] != -1:
                dp[idx][i] = max(dp[idx][i] , dp[idx][i - sz] + value)

# 01背包结束，开始把dp的结果当作物品继续进行01背包
f = [-1] * (c + 1)
# 一开始f[0] 合法，是因为需要让第一个分组能够成功转移
# 大家可以考虑下如果一开始f[0] = -1 , 对于第一个分组的转移会有什么影响?
f[0] = 0
for idx in a:
    # 过程中的tmp[0]却是不合法的了(不再像一开始一样f[0] = 0了)，
    # 这是因为之前已经有考虑过至少一个分组了
    # 因为假设tmp[0] = 0,那么就是假设前面若干组都可以不选哪怕一
    # 个进程,这个是违反题意的
    tmp = [-1] * (c + 1)
    # i 为总共大小
    for i in range(c + 1):
        # j是当前分组分配的大小
        # j从1开始是为了让当前分组至少有选进程
        for j in range(1 , i + 1):
            if f[i - j] != -1 and dp[idx][j] != -1:
                tmp[i] = max(tmp[i] , f[i - j] + dp[idx][j])
    f = tmp.copy()
print(max(f))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读入 n, m, c
        int n = sc.nextInt();
        int m = sc.nextInt();
        int c = sc.nextInt();
        
        // 使用 HashMap 作为哈希表
        HashMap<Integer, List<int[]>> a = new HashMap<>();
        
        // 读入数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int idx = sc.nextInt();
                int sz = sc.nextInt();
                int value = sc.nextInt();
                a.putIfAbsent(idx, new ArrayList<>());
                a.get(idx).add(new int[]{sz, value});
            }
        }
        
        // 先对每个分组进行01背包
        HashMap<Integer, int[]> dp = new HashMap<>();  // 使用HashMap存储每个分组的dp结果
        
        for (Map.Entry<Integer, List<int[]>> entry : a.entrySet()) {
            int idx = entry.getKey();
            dp.put(idx, new int[c + 1]);
            Arrays.fill(dp.get(idx), -1);
            dp.get(idx)[0] = 0;  // 初始时，大小为0时价值为0
            
            for (int[] item : entry.getValue()) {
                int sz = item[0];
                int value = item[1];
                // 从后往前遍历，确保01背包的更新
                for (int i = c; i >= sz; i--) {
                    if (dp.get(idx)[i - sz] != -1) {
                        dp.get(idx)[i] = Math.max(dp.get(idx)[i], dp.get(idx)[i - sz] + value);
                    }
                }
            }
        }
        
        // 01背包结束，开始把 dp 的结果当作物品继续进行01背包
        int[] f = new int[c + 1];
        Arrays.fill(f, -1);
        f[0] = 0;  // 一开始 f[0] 合法，是因为需要让第一个分组能够成功转移
        
        for (Map.Entry<Integer, List<int[]>> entry : a.entrySet()) {
            int idx = entry.getKey();
            int[] tmp = new int[c + 1];
            Arrays.fill(tmp, -1);
            
            // i 为总共大小
            for (int i = 0; i <= c; i++) {
                // j 是当前分组分配的大小
                for (int j = 1; j <= i; j++) {
                    if (f[i - j] != -1 && dp.get(idx)[j] != -1) {
                        tmp[i] = Math.max(tmp[i], f[i - j] + dp.get(idx)[j]);
                    }
                }
            }
            f = tmp.clone();  // 更新 f 数组
        }
        
        // 输出结果
        int result = Arrays.stream(f).max().getAsInt();
        System.out.println(result);
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    
    unordered_map<int, vector<pair<int, int>>> a;  // 使用unordered_map实现哈希表
    
    // 读入数据
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int idx, sz, value;
            cin >> idx >> sz >> value;
            a[idx].emplace_back(sz, value);  // 把物品信息存入哈希表
        }
    }
    
    // 先对每个分组进行01背包
    unordered_map<int, vector<int>> dp;  // 使用unordered_map存储每个分组的dp结果
    
    for (auto &entry : a) {
        int idx = entry.first;
        dp[idx] = vector<int>(c + 1, -1);
        dp[idx][0] = 0;  // 初始时，大小为0时价值为0
        
        for (auto &item : entry.second) {
            int sz = item.first, value = item.second;
            // 从后往前遍历，确保01背包的更新
            for (int i = c; i >= sz; --i) {
                if (dp[idx][i - sz] != -1) {
                    dp[idx][i] = max(dp[idx][i], dp[idx][i - sz] + value);
                }
            }
        }
    }
    
    // 01背包结束，开始把 dp 的结果当作物品继续进行01背包
    vector<int> f(c + 1, -1);
    f[0] = 0;  // 一开始f[0] 合法，是因为需要让第一个分组能够成功转移
    
    for (auto &entry : a) {
        int idx = entry.first;
        vector<int> tmp(c + 1, -1);
        
        // i 为总共大小
        for (int i = 0; i <= c; ++i) {
            // j是当前分组分配的大小
            for (int j = 1; j <= i; ++j) {
                if (f[i - j] != -1 && dp[idx][j] != -1) {
                    tmp[i] = max(tmp[i], f[i - j] + dp[idx][j]);
                }
            }
        }
        f = tmp;
    }
    
    // 输出结果
    cout << *max_element(f.begin(), f.end()) << endl;
    return 0;
}