本题几乎全部题解都使用的是二分。时间复杂度为 $O(n \log W)$。

但是本题可以实现 $O(n)$ 的复杂度。不过只有唯一一篇题解提及了这种做法，而且说得比较含糊。于是便有了本文。

本文使用了斜率优化。链接：https://www.luogu.com/article/fcxm53nu