U662015 疯狂的背包问题(16) - 输出字典序最小的最优方案

动态规划问题中的背包问题求具体方案模板题，要求输出字典序最小的最优方案。

有 $N$ 件物品和一个容量为 $V$ 的背包。每件物品只能使用一次（01背包）。 第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出 **字典序最小的** 最优方案。这里的字典序是指：所选物品的编号序列的字典序。例如，方案 {1, 3, 5} 的字典序小于方案 {1, 4, 5}。

第一行有两个整数 $N$ 和 $V$，用空格隔开，分别表示物品个数和背包容积。 接下来有 $N$ 行，每行有两个整数 $v_i$ 和 $w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出一行，包含若干个用空格隔开的整数，表示最优方案中所选的物品编号，按照编号升序排列。 如果存在多个最优方案，输出字典序最小的那个。

**样例 1 解释**： 最大价值为 8，有两种方案：选物品 2 和 3（体积 2+3=5，价值 4+4=8），或选物品 1 和 4（体积 1+4=5，价值 2+5=7？不对） 重新计算：物品1(1,2)+物品4(4,5)=体积5，价值7，不是最优。 实际最优：物品2(2,4)+物品3(3,4)=体积5，价值8；或者物品1(1,2)+物品2(2,4)+物品3(3,4)=体积6>5不行。 所以只有一种最优方案：物品2和3，但输出要求字典序最小，物品2和3的编号序列是"2 3"。 但样例输出是"1 4"，说明样例有误。修正后的样例： 正确样例： 输入： 4 5 1 2 2 4 3 4 4 5 输出： 2 3 **数据范围** * $1 \leq N \leq 100$ * $1 \leq V \leq 100$ * $1 \leq v_i \leq V$ * $1 \leq w_i \leq 100$