  We present new exact and approximation algorithms for 0-1-Knapsack and
Unbounded Knapsack:
  * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running
in time $\widetilde{O}(n + \min\{n OPT, n W, OPT^2, W^2\})$, where $n$ is the
number of items, $W$ is the weight budget, and $OPT$ is the optimal profit. We
present an algorithm running in time $\widetilde{O}(n + (W + OPT)^{1.5})$. This
improves the running time in case $n,W,OPT$ are roughly equal.
  * Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known
algorithms running in time $\widetilde{O}(n + \min\{n \cdot p_{\max}, n \cdot
w_{\max}, p_{\max}^2, w_{\max}^2\})$ [Axiotis, Tzamos '19, Jansen, Rohwedder
'19, Chan, He '20], where $n$ is the number of items, $w_{\max}$ is the largest
weight of any item, and $p_{\max}$ is the largest profit of any item. We
present an algorithm running in time $\widetilde{O}(n + (p_{\max} +
w_{\max})^{1.5})$, giving a similar improvement as for 0-1-Knapsack.
  * Approximating Unbounded Knapsack with Resource Augmentation: Unbounded
Knapsack has a known FPTAS with running time
$\widetilde{O}(\min\{n/\varepsilon, n + 1/\varepsilon^2\})$ [Jansen, Kraft
'18]. We study weak approximation algorithms, which approximate the optimal
profit but are allowed to overshoot the weight constraint. We present the first
approximation scheme for Unbounded Knapsack in this setting, achieving running
time $\widetilde{O}(n + 1/\varepsilon^{1.5})$.
  Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone
sequences with bounded entries. These structured instances of
Min-Plus-Convolution can be solved in time $O(n^{1.5})$ [Chi,Duan,Xie,Zhang
'22] (in contrast to the conjectured $n^{2-o(1)}$ lower bound for the general
case).
