# Queries on unbounded knapsack

Given $$n$$ types of items with integer cost $$c_{i}$$ (there is an unlimited number of items of each type), such that $$c_{i} \leq c$$ for all $$i = 1, 2, \dots, n$$, answer (a lot of) queries of form "is there some set of items of total weight $$w$$?" in time $$O(1)$$ with some kind of precalculation in time $$O(n c \log c)$$.

I've got a hint - for every $$i = 0, 1, 2, \dots, c - 1$$ find minimal $$x$$ such that there is a set of items with total weight $$x$$ and $$x \equiv i \quad (\bmod c)$$. How to calculate all $$x$$'s and how to use them to answer the queries?

This problem is somehow related to graphs and shortest paths, but I don't understand the connection between actual knapsack-like thing and graphs (maybe there is some graph with paths of desired weight?).

Source: problem 76 on neerc.ifmo.ru wiki.

• Try the techniques shown here: cs.stackexchange.com/tags/dynamic-programming/info. That said, I don't understand the hint; I wonder if it's not quite right. For instance, if $c_1=17$, $c_2=19$, $c=20$, I don't see how the hint helps. Can you edit your question to credit the original source of this exercise, please? – D.W. Mar 29 at 18:54
• @D.W. I've added the source (by the way, the original statement is in Russian). – cyril2020 Mar 29 at 19:03
• Thanks! I have some suggestions. Can you solve it first with $n=2$? If so, show your solution. Can you solve it with $n=3$? Show your solution. I am not sure whether the hint is 100% right. Maybe consider the following variant of the hint as well: replace the $c$ in the hint with a different variable $d$; figure out how to solve the hint for arbitrary $d$; and then pick how to set $d$. I don't know how to solve it for arbitrary $n$, so I am not sure whether these will lead to a solution, but they "smell" promising to me. – D.W. Mar 29 at 19:33