#P12258. [蓝桥杯 2024 国 Java B] 背包问题
[蓝桥杯 2024 国 Java B] 背包问题
题目描述
神奇商店中一共有 种不同的物品,第 种物品的重量为 ,每种物品的数量都是无限个。店主会从中挑选任意种商品,每种商品可以选择任意个并将其装入到一个背包之中,从而可以组合出多种背包(这个背包可以容纳无限多的物品),其中背包的重量就是其中所含物品的重量之和。
小蓝想要的背包中至少要有 件物品。小蓝想要知道,在所有满足他要求的背包中,如果将背包重量从小到大排序并去除重复的重量,排名第 的重量是多少。
输入格式
第一行输入三个整数,用空格分隔,依次是 、、。
第二行输入 个用空格分隔的整数表示 件物品的重量。
输出格式
输出一行,包含一个整数表示答案。
7 2 7
84 21 12 3 65 5 41
13
提示
样例说明
背包中物品个数大于等于 时,从小到大依次出现的背包重量为:
、、、、、、。
评测用例规模与约定
- 对于 的评测用例,,。
- 对于 的评测用例,,,,