Let $N = \{1, 2, \ldots, n\}$ denote a set of items, $w \in \mathbb{R}_{++}^N$ a vector of weights, $c > 0$ a constant and $x \in \{0, 1\}^N$ a decision variable. The objective is to minimally under-/ overload the knapsack, i.e. $$ J(x; w, c) = \left|c - \sum_{i \in N}{x_i \cdot w_i}\right|. $$ We consider the problem $\min_x J(x; w, c)$.
Example For $N = \{1, 2, 3\}$, $w = (1, 3, 7)$ and $c \in \{5,6\}$ the solution is respectively given by \begin{align} &(1, 1, 0) = \min_x J(x; w, 5)\\ &(0, 0, 1) = \min_x J(x; w, 6) \end{align}
- Is this a known problem?
- Are there any algorithms to solve the problem?
The $0 - 1$ knapsack problem is NP-Complete. There is however a pseudo-polynomial time dynamic programming algorithm $P(n, c, w)$ that runs in $f(n, c) = O(nc)$ time with $n$ the number of items to choose from and $c$ the capacity of the knapsack. We can use this algorithm to compute the minimum of $J = \vert c - \sum_{i \in N} x_i \cdot w_i \vert$.
For example, to compute the desired minimum we can repeatedly use $P(n, c, w)$, progressively reducing a capacity $t$ until we get a set of items whose collective weight $s$ is closest to $c$.
Here is the algorithm. We start with a capacity $t = c + m$ with $m$ the weight of the heaviest item. Then we use $P(n, c, w)$ to compute the maximum weight $s$ we can store in the knapsack without exceeding $t$. Then we subtract $1$ from $t$ to get a new capacity $t = t - 1$, from which we compute the new maximum weight $s$. We repeat until we have found the minimum absolute difference $J = \vert s - c \vert$, which is at some $t \geq c$.
The time complexity $T(n, c)$ of this algorithm is:
$$ T(n, c) = \sum_{k = 0}^m f(n, c + m - k) = m \cdot O(n(c + m)) = O(ncm + nm^2) $$
If we assume that $m$ differs from $c$ by only a constant factor, we get $O(nc^2)$.