# Queries on knapsack

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.

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

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$$.