题目大意

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

思路

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

step1:整体分配

题目内容

有一个日志管理系统，保存了$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$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写