← 返回 xai 的题目列表Determine large rice bags
类型：online_judge
Given a list of integers that represent the capacity of rice bags, design an algorithm to determine how to select bags such that their total capacity exceeds a given target. Output the sequence of selected bags and their total capacity. Assume there's at least one possible solution. The input includes an integer array and a target value.
Input:
The first line is an integer `n` representing the number of rice bags.
The second line contains `n` integers representing the capacity of each rice bag.
The third line is the target value, the minimum total capacity needed.
Output Requirement:
Indexes of selected rice bags (starting from 0), and the total capacity of these bags should meet or exceed the target capacity.
Constraints:
- 1 <= n <= 10^5
- Each rice bag capacity ranges from 1 to 1000.
Example:
Input:
5
1 3 5 7 9
15
Output:
[1, 3, 4]
Total: 19
Example
Input
5
1 3 5 7 9
15