  We study the $K$-item knapsack problem (i.e., $1.5$-dimensional KP), which is
a generalization of the famous 0-1 knapsack problem (i.e., $1$-dimensional KP)
in which an upper bound $K$ is imposed on the number of items selected. This
problem is of fundamental importance and is known to have a broad range of
applications in various fields. It is well known that, there is no FPTAS for
the $d$-dimensional knapsack problem when $d\geq 2$, unless P $=$ NP. While the
$K$-item knapsack problem is known to admit an FPTAS, the complexity of all
existing FPTASs have a high dependency on the cardinality bound $K$ and
approximation error $\varepsilon$, which could result in inefficiencies
especially when $K$ and $\varepsilon^{-1}$ increase. The current best results
are due to Mastrolilli and Hutter (2006), in which two schemes are presented
exhibiting a space-time tradeoff--one scheme with time complexity
$O(n+Kz^{2}/\varepsilon^{2})$ and space complexity $O(n+z^{3}/\varepsilon)$,
while another scheme requires $O(n+(Kz^{2}+z^{4})/\varepsilon^{2})$ run-time
but only needs $O(n+z^{2}/\varepsilon)$ space, where
$z=\min\{K,1/\varepsilon\}$. In this paper we close the space-time tradeoff
exhibited in the state-of-the-art by designing a new FPTAS with a run-time of
$\widetilde{O}(n+z^{2}/\varepsilon^{2})$, while simultaneously reaching the
$O(n+z^{2}/\varepsilon)$ space bound. Our scheme provides $\widetilde{O}(K)$
and $O(z)$ improvements on the state-of-the-art algorithms in time and space
complexity respectively, and is the first scheme that achieves a run-time that
is independent of cardinality bound $K$ (up to logarithmic factors) under fixed
$\varepsilon$. Another salient feature of our scheme is that it is the first
FPTAS that achieves better time and space complexity bounds than the very first
standard FPTAS over all parameter regimes.
