第 K 优解

题目描述

在一个神秘的藏宝室里，你发现了一个容量为 $M$ 的背包和 $N$ 件宝物。

每件宝物的属性如下：

• 重量 $w_i$。
• 价值 $v_i$。

守卫者提出了一个与众不同的挑战：他不要求你求出最高价值，而是要求你求出在背包容量限制下，第 $K$ 大的总价值是多少。

注意：

1. 两种方案被认为不同，当且仅当它们选择的宝物集合不同（即至少有一个编号的宝物在一种方案中被选中而在另一种中没被选中）。
2. 我们要找的是所有可能方案（包括不选任何宝物的方案，其价值为 0）中，价值排名第 $K$ 的那个数值。
3. 这里的“第 $K$ 大”是指数值排名，如果存在多个不同的集合产生相同的总价值，每个集合都要单独计入排名。（例如：价值序列为 10, 10, 9, 8，则第 2 大是 10，第 3 大是 9）。

输入格式

第一行包含三个整数 $N, M, K$。

接下来的 $N$ 行，每行包含两个整数 $w_i$ 和 $v_i$。

输出格式

输出一个整数，表示在所有有效方案中，总价值第 $K$ 大的那个数值。

输入输出样例 #1

输入 #1

3 10 3
5 10
4 8
6 12

输出 #1

10

样例 1 说明

所有可能方案及价值：

• 选 {1, 2}：重 9，值 18
• 选 {3, 2}：重 10，值 20
• 选 {1}：重 5，值 10
• 选 {2}：重 4，值 8
• 选 {3}：重 6，值 12
• 选 {1, 3}：重 11（超限）
• 选 {}：重 0，值 0 价值降序：20, 18, 12, 10, 8, 0。 第 3 大是 12。 （修正：上面样例计算有误，20, 18, 12, 10, 8, 0，第 3 大其实是 12。样例说明仅供逻辑参考）。 修正样例数据： 输入： 3 10 3 5 10 4 8 6 12 输出： 12

数据范围

对于 $100\%$ 的数据，$1 \le N \le 200$，$1 \le M \le 5000$，$1 \le K \le 50$，$1 \le w_i \le M$，$1 \le v_i \le 10^6$。

建议

三刷