题目大意

一个拥有一定容量的背包，有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;
}

题目内容

有一个日志管理系统，保存了$N$个进程的日志文件，每个进程有$M$个日志文件。系统记录了每个日志文件的文件大小和被下载的次数。现在需要把部分日志文件保存在容量为$c$的$U$盘中，请设计算法计算$U$盘存储的日志文件下载次数之和最大是多少。 注意，为了保证日志的完整性，每个进程至少要保存一个日志文件到$U$盘，如果无法实现，则返回$-1$，如果$U$盘容量足以存储，则返回所存储的日志文件被下载的次数之和。

输入描述

入参分为多行输入:

• 第$1$行输入的输入信息是$N、M、C$,用空格分割。
• 第$2$行开始是日志文件的信息，每行信息包含了所属进程序号、文件大小和被下载次数，用空格分割。

输出描述

$U$盘存储的日志文件被下载次数之和，每个进程至少要保存一个日志文件到$U$盘，如果无法实现，则返回$-1$。

样例1

输入

1 2 10
0 5 1
0 5 2

输出

3

说明

有$1$个进程，每个进程有$2$个日志文件，$U$盘容量是$10$。第一个进程的第一个文件大小是$5$，下载次数是$1$;第一个进程的第二个文件大小是$5$，下载次数是$2$。$U$盘能存储这两个文件，下载次数之和最多是$3$次。

样例2

输入

2 2 10
0 5 1
0 5 2
1 6 1
1 6 2

输出

-1

说明

有$2$个进程，每个进程有$2$个日志文件，$U$盘容量是$10$。第一个进程的第一个文件大小是$5$，下载次数是$1$;第一个进程的第二个文件大小是$5$，下载次数是$2$。第二个进程的第一个文件大小是$6$，下载次数是$1$;第二个进程的第二个文件大小是$6$，下载次数是$2$。U盘容灾无法确保每个进程至少存入一个文件，返回$-1$。