  We study pseudo-polynomial time algorithms for the fundamental \emph{0-1
Knapsack} problem. In terms of $n$ and $w_{\max}$, previous algorithms for 0-1
Knapsack have cubic time complexities: $O(n^2w_{\max})$ (Bellman 1957),
$O(nw_{\max}^2)$ (Kellerer and Pferschy 2004), and $O(n + w_{\max}^3)$ (Polak,
Rohwedder, and W\k{e}grzycki 2021). On the other hand, fine-grained complexity
only rules out $O((n+w_{\max})^{2-\delta})$ running time, and it is an
important question in this area whether $\tilde O(n+w_{\max}^2)$ time is
achievable. Our main result makes significant progress towards solving this
question:
  - The 0-1 Knapsack problem has a deterministic algorithm in $\tilde O(n +
w_{\max}^{2.5})$ time.
  Our techniques also apply to the easier \emph{Subset Sum} problem:
  - The Subset Sum problem has a randomized algorithm in $\tilde O(n +
w_{\max}^{1.5})$ time.
  This improves (and simplifies) the previous $\tilde O(n +
w_{\max}^{5/3})$-time algorithm by Polak, Rohwedder, and W\k{e}grzycki (2021)
(based on Galil and Margalit (1991), and Bringmann and Wellnitz (2021)).
  Similar to recent works on Knapsack (and integer programs in general), our
algorithms also utilize the \emph{proximity} between optimal integral solutions
and fractional solutions. Our new ideas are as follows: - Previous works used
an $O(w_{\max})$ proximity bound in the $\ell_1$-norm. As our main conceptual
contribution, we use an additive-combinatorial theorem by Erd\H{o}s and
S\'{a}rk\"{o}zy (1990) to derive an $\ell_0$-proximity bound of $\tilde
O(\sqrt{w_{\max}})$. - Then, the main technical component of our Knapsack
result is a dynamic programming algorithm that exploits both $\ell_0$- and
$\ell_1$-proximity. It is based on a vast extension of the ``witness
propagation'' method, originally designed by Deng, Mao, and Zhong (2023) for
the easier \emph{unbounded} setting only.
