题目中最难处理的地方之一，是你构造出来的重量和价值的上下界也是 $[1,10^9]$。
不过我们可以先把限制放宽，考虑更容易构造的版本。
重量的上下界是 $[0,10^9]$，价值的上下界是 $[0,10^9+1]$
设已经确定重量的物品集合为 $S$，未确定重量的物品集合为 $T$。
将 $S$ 按 $(w_i,i)$ 升序排序，将 $T$ 按 $(r_i,-i)$ 降序排序。
那么，从 Alice 的重量贪心角度看，她最终选中的一定是 $S$ 的一个前缀，以及 $T$ 中的一部分物品。
于是我们枚举这个前缀长度，设 Alice 会选中 $S_1,S_2,\cdots S_k$，而 $S_{k+1}$ 及之后的物品绝对不会被选中。
为了让 Bob 也选出同样的集合，我们要让应该被选中的物品尽量靠前，不应该被选中的物品尽量靠后。
因此，对于 $S$ 中价值未确定的物品，我们这样赋值：
若它属于前缀 $S_1,S_2,\cdots S_k$，就把它的价值设为 $10^9+1$；
若它属于后缀 $S_{k+1},S_{k+2},\cdots$，就把它的价值设为 $0$。
这样，Bob 的价值贪心会优先考虑我们希望保留的那些物品。
为了避免选中 $S_{k+1}$，我们必须精心构造 $T$ 中物品的重量，使得 Alice 和 Bob 在考虑 $S_{k+1}$ 之前，选中 $T$ 中的部分物品，使得剩余的背包容量都不足以容纳 $S_{k+1}$。
由于允许重量为 $0$，而重量为 $0$ 的物品一定会被选中，相当于不存在。于是我们让 $T$ 中所有的物品都被选中，精心构造它们的重量，让它们尽可能占用背包大量的空间，以阻止物品 $S_{k+1}$ 的选中。
令 $W_r$ 表示背包目前还可容纳的重量，初始时 $$ W_r=W-\sum_{i=1}^k w_{S_i}. $$
给我们指定的物品 $T_i$ 确定重量 $w_{T_i}$ 时，有以下约束：
- $w_{T_i}\le W_r$，这是为了使得给背包预留足够的容量。
- $w_{T_i}< w_{S_{k+1}}$。特别地，如果指定的物品下标在 $S_{k+1}$ 之前，则是 $w_{T_i}\le w_{S_{k+1}}$。否则 Alice 选中这个元素的时机会晚于 $S_{k+1}$，没有任何效果。
而为了让 Bob 选中这些「占空间」元素的时机尽可能早，我们在 $T$ 中从前往后贪心执行上述过程。
初始令 $W_r=W-\sum_{i=1}^k w_{S_i}$，然后考虑到 $T_i$ 时，将其重量设为 $w_{T_i}=\min(W_r,w_{S_{k+1}}-1)$（或 $w_{T_i}=\min(W_r,w_{S_{k+1}})$，取决于 $T_i$ 与 $S_{k+1}$ 的位置关系），然后 $W_r\gets W_r-w_{T_i}$。
上面的构造是「朝着成功方向去」的，但不保证一定合法。
所以每次枚举前缀后，我们都要 $O(n\log n)$ 模拟一次 Alice 和 Bob 的贪心，检查最终选出的集合是否完全相同。
若相同，就说明这个前缀对应的构造可行；否则继续枚举下一个前缀。
时间复杂度为 $O(n^2\log n)$。
重量的上下界是 $[0,10^9]$
此时价值不允许有 $0$ 和 $10^9+1$ 了，我们一个直观的想法是将价值为 $0$ 的物品的价值变成 $1$，把价值为 $10^9+1$ 的物品的价值变成 $10^9$。事实上这是对的。
这里要强调一件事，我们不是在说「任意一个在放宽版本里合法的方案，压缩以后仍然合法」；我们真正要证明的是：如果原题有解，那么我们上面这套构造，在压回到 $[1,10^9]$ 以后，仍然能给出一个合法方案。
重量的上下界是 $[1,10^9+1]$
此时重量不允许有 $0$ 了，但是允许重量存在 $10^9+1$。
当一个物品重量为 $0$ 时，其必然会被选中。
当一个物品重量为 $10^9+1$ 时，其必然不会被选中。
所以这两者是一样的，我们将重量为 $0$ 的重量变成 $10^9+1$ 即可。
无额外约束
此时重量不允许有 $10^9+1$ 了。我们一个直观的想法是，将所有重量为 $10^9+1$ 的重量变成 $10^9$。但这并不对。
问题在于，我们是不希望「原本重量为 $10^9+1$」的物品被选中的。但是场面上存在一些「原本重量为 $10^9$」的物品。如果单纯将重量为 $10^9+1$ 的物品重量改为 $10^9$，同时还比「原本重量为 $10^9$」的物品的下标还前，那么就会被选中，这是我们不想看到的。
将「原本重量为 $10^9$」的物品分为两类，分别是「原本被确定重量是 $10^9$ 的」，以及「后面被我们确定重量为 $10^9$ 的」。前者我们无能为力，但是后者似乎可以分析一下。
回忆一下，我们自己确定 $T$ 中重量时，确定的重量需要对 $W_r$ 取 $\min$，$W_r\le W$。
$W_r$ 能够取到 $10^9$，需要满足几个极其严苛的条件：
- $W=10^9$
- $k=0$
- $w_{S_1}=10^9$（这是因为 $w_{S_{k+1}}=10^9$）
- $S_1>T_1$（只有 $S_{k+1}$ 在当前考虑的元素后面时才能取到等号，而且只有 $T_1$ 的 $w$ 可能取到 $10^9$，后面的 $W_r$ 至少会在 $B_1$ 这里减去 $1$）
上面这几条条件如果存在不满足的，直接将重量为 $10^9+1$ 的重量变成 $10^9$ 是可行的。
否则，由于 $S$ 按照重量从小到大排，而 $w_{S_1}=10^9$，所以 $\forall i\in [1,|S|]$，都有 $w_{S_i}=10^9$。
于是，我们将 $w_{T_1}$ 设为 $10^9-1$，其余 $T$ 中元素全部设为 $10^9$。此时从重量策略来看，我们只会选择 $T_1$；而从价值策略来看，根据我们上面的构造，我们会把 $S$ 中所有未确定价值的物品的价值设为 $1$，也就是尽可能提前 $T_1$ 的优先级，如果 $T_1$ 是第一个被考虑的元素，那么我们也只会选择 $T_1$。综上，构造完毕。
更优美的实现
在上文中，我们需要特判一种情况，这很不优美。一种方法是，在考虑 $T$ 中物品的重量 $w$ 时，令其为 $w_{T_i}=\min(W_r,w_{S_{k+1}}-1,10^9-1)$（或 $w_{T_i}=\min(W_r,w_{S_{k+1}},10^9-1)$），这样写会更统一，也更好实现。
总结一下大致流程：
- 将 $S$ 按 $(w_i,i)$ 升序排序，将 $T$ 按 $(r_i,-i)$ 降序排序；
- 枚举 $S$ 的一个前缀 $S_1,\cdots ,S_k$，将前缀的未定义价值的物品的价值设为 $10^9$，将后缀未定义价值的物品的价值设为 $1$；
- 顺序枚举 $T_i$，令 $w_{T_i}=w=\min(W_r,w_{S_{k+1}}-1,10^9-1)$ 或 $w_{T_i}=\min(W_r,w_{S_{k+1}},10^9-1)$。如果 $w_{T_i}=0$，则将其赋值为 $10^9$；
- 判定是否构造正确，如果不是则继续枚举前缀。