题解

思路

从编号最大的物品向前考虑，并维护当前剩余容量 $R$ 与已经确定选入的较大编号物品价值和 $cur$。

做法

若 $R<w_i$，物品 $i$ 不可能选，只需继续；若 $R\ge w_i$，选择它后把 $R$ 减去 $w_i$、把 $v_i$ 加入 $cur$，而不选择它时，由 $\sum_{j<i}w_j<w_i\le R$ 可知所有更小编号物品一定能同时装下，又因为价值均为正，此分支的最优值就是 $cur+\sum_{j<i}v_j$，可以当场更新答案而无需继续搜索。

依次记录每个“第一次放弃本可选物品”的分支，再加上始终选择所有能选物品的分支，就覆盖了全部最优候选。

复杂度

预处理价值前缀和后，每件物品只处理一次，总时间复杂度为 $O(N)$，空间复杂度为 $O(N)$；价值总和最多为 $6\times10^{17}$，需使用 64 位整数。