g6-07962. 哪些物品可能被选 未做

小杨有 $n$ 件物品，第 $i$ 件重 $w_i$、价值 $v_i$，背包容量为 $V$，每件物品至多选一次。先求出最大总价值 $OPT$，再输出 $n$ 个数字：第 $i$ 位为 $1$ 当且仅当存在一个总价值为 $OPT$ 的方案包含第 $i$ 件物品，否则为 $0$。

第一行两个整数 $n,V$。

接下来 $n$ 行，每行两个整数 $w_i,v_i$。

第一行一个整数 $OPT$；第二行 $n$ 个 0/1 数字。

输入 1

3 5
2 3
2 3
3 4

输出 1

7
111

最优值 7；三个最优方案（1+3、2+3、1+2？注意 1+2 只得 6）——实际为 1+3 与 2+3，三件物品都出现在某个最优方案中，故输出 111。

$1\le n\le 12$，$1\le V\le 100$，$1\le w_i,v_i\le 30$。