规划艾泽拉斯

[陈青扬]

题目描述
你现在是艾泽拉斯的主席，需要举办一场盛大的活动，活动由许多项目组成且最长持续时间为
�
T。每个项目都有各自的持续时间
�
�
t
i
​
，你希望在不超过最长持续时间
�
T的情况下，尽可能的选择项目，使得项目持续时间之和最大，并输出每个所选的项目持续时间。

输入示例
多组输入，第一行输入一个整数
�
(
1
≤
�
≤
1000
)
S(1≤S≤1000)，表示测试数据的组数。

接下来每一行首先输入两个整数
�
(
1
≤
�
≤
1000
)
T(1≤T≤1000)和
�
(
1
≤
�
≤
2000
)
N(1≤N≤2000)，表示活动最长持续时间和项目数。接下来输入
�
N个整数
�
1
,
�
2
,
.
.
.
,
�
�
(
1
≤
�
�
≤
�
)
t
1
​
,t
2
​
,…,t
n
​
(1≤t
t
​
≤T)，表示每个活动的持续时间。

保证所有数据
�
N的总和不超过
2000
2000。

输出示例
对于每组测试数据，输出一组整数表示所选项目的持续时间，最后输出一个整数表示持续时间之和。

可能会有多种输出项目时间的方法，优先输出以项目下标为字典序最小的情况。

样例#1
输入样例#1
5
5 5 1 2 3 4 5
10 9 11 9 3 5 8 4 9 3 2
16 8 12 6 11 11 13 1 10 7
13 5 10 12 2 13 10
28 14 18 19 26 15 18 24 7 21 14 25 2 12 9 6
输出样例#1
1 4 5
3 5 2 10
6 10 16
13 13
19 7 2 28
样例说明
对于第二组数据，可能的输出情况有
[
3
,
5
,
2
]
,
[
3
,
4
,
3
]
,
[
5
,
3
,
2
]
,
[
8
,
2
]
[3,5,2],[3,4,3],[5,3,2],[8,2]，其对应的下标序列分别为
(
3
,
4
,
9
)
,
(
3
,
6
,
8
)
,
(
4
,
8
,
9
)
,
(
5
,
9
)
(3,4,9),(3,6,8),(4,8,9),(5,9)。下标序列字典序最小的为
(
3
,
4
,
9
)
(3,4,9)，所以我们输出
[
3
,
5
,
2
]
[3,5,2]。

[信友队汪老师 (汪老师)]

注意一下发帖规则：

1. 最好把问题发在自己的等级类别里，不要轻易发到 常规 分类里。
2. 发帖时选择题号，就不需要粘贴问题描述了。

[信友队汪老师 (汪老师)]

这是一道 01背包 变形题（其实也比较经典啦）。
不仅要求最长的持续时间，关键还要输出具体选择的数字。
类比于迷宫题，不仅要求出最短步数，还要输出具体的路径。

首先要知道：01背包的路径推导其实就是01背包的逆运算。
即：如果计算的顺序是从第1个到第n个元素，那么求路径就要反过来。

同时这题又要求所选数字的序号字典序尽可能小。
按照贪心的思想，前面序号小的元素如果能选，就尽量选。

综上两点，这里的01背包的DP顺序应该是从后往前，即从最后一个输入的元素开始计算，这样在求路径时就能从第1个元素开始啦。

确定了计算方向，但是具体怎么算呢？

有两种做法：

1. 标记法：创建一个二维标记数组（大小同二维dp数组），在DP的同时标记可选的DP位置，然后根据此数组反推能选的数字。

2. 推断法：使用二维dp数组计算，然后根据dp数组前后元素的关系判断是否能选。

具体来说，从dp数组存储最终结果的元素开始，判断当前元素是否可以被选中（在满足最大化结果的前提下），如果可以，则减去当前元素的 “价值”（活动时间），跳转到前一个元素的对应位置（参考状态转移方程做逆运算），以此类推，直到 “价值” 减为0或遍历完所有元素。

用题目中的第一组数据来看：

5 5 1 2 3 4 5

首先要注意，此图对应的输入顺序是从前往后（序号从 1 到 N ），但 DP 的计算顺序是从 N 到 1 的，所以最终的最大结果是存储在 dp[1][T]，而不是 dp[N][T] 。

如果要凑到 5，其实有 3 种方式：

1. 1 + 4 = 5
2. 2 + 3 = 5
3. 5 = 5

但这里要序号字典序最小的，所以输出的是：1 4
后面再带上最大的结果：5

参考代码：