2
$\begingroup$

Given items with weights $w_{1}, w_{2}, \dots, w_{n}$ and queries of form $(l, r, w)$ asking for possibility to find a subset of items $w_{l}, w_{l + 1}, \dots, w_{r}$ with total weight $w$, how to answer these queries with $O(1)$ time by having done precalculation of some table in $O(nW)$ time, where W is strict upper bound for $w_{i}$.

The time for precalculation looks similar to the straight 0-1 knapsack, but here I can't see what we really should put in the table.

$\endgroup$
  • $\begingroup$ Are you sure $W$ is the upper bound for $w_i$, rather than $\sum w_i$? $\endgroup$ – xskxzr Nov 1 '19 at 7:42
1
$\begingroup$

I'm assuming that $W$ is an integer upper bound to $\sum_i w_i$, as asked by xskxzr, that all $w_i$ are positive integers, and that the values $w$ in the queries are also integers upper bounded by $W$.

For $i \ge 1$, let $S[i,w]$ be the largest index $j \in \{1, \dots, i\}$ such that it is possible to select a subset of $\{w_k : j \le k \le i \}$ of weight $w>0$. If no such index $j$ exists, or if $w \le 0$, let $S[i,w] = -\infty$.

According to the above definition:

  • For $w \neq w_1$, $S[1,w] = - \infty$.

  • For $i \ge 1$, $S[i,w_i] = i$.

  • For $i>1$, and $w \neq w_i$, $S[i,w] = \max \begin{cases} S[i-1,w] & \\ S[i-1,w-w_i] & \end{cases} $

There are only $O(n W$) "interesting" values of $S[i,w]$ to compute (namely those with $i=1,\dots,n$ and $w=1,\dots,W$), each of which can be found in constant time.

To answer a query $(l,r,w)$ proceed as follows (pick the first condition that applies):

  • If $w = 0$, return true (the subset you're looking for is the empty set);
  • If $w < 0$, return false;
  • If $r < 1$, return false (since, at this point, $w \neq 0$).
  • return true if and only if $S[\min\{r,n\},w] \ge l$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.