1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Mar 29 at 18:54
  • $\begingroup$ @D.W. I've added the source (by the way, the original statement is in Russian). $\endgroup$ – cyril2020 Mar 29 at 19:03
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 29 at 19:33

Your Answer

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

Browse other questions tagged or ask your own question.