Multiple choice knapsack dynamic programming

Question

Giving a the following:

A list of a store items $T=\{t_1, t_2,...,t_n\}$.

A list of prices of each item $P=\{p_1, p_2,...,p_n\}$.

A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$respectively.

And total bill $M$.

Our goal is to find any possible list of items that its total value is equal to $M$ using dynamic programming.

My question does 0/1 weighted Knapsack problem help, where $M$ can be the capacity of the knapsack, and the weight of each item equal to the quantity of the item. If there is any other better approach I would appreciate any references.

Answer 1

It turned out we can achieve it in $O(nM)$ time where $n$ is the number of distinct items in the store, and $M$ is the final bill.

We can build a 2-dimensional array with size $C[T, M]$ as follows:

$C[i, j] = 1$, if there exists a way to add items from $\{t_1,t_2,...,t_i\}$ that adds up to $M$.

$C[i, j] = 0$, if we cannot find items that adds up to $M$.

Finally, it's useful to use one extra row and column to make the calculation easier in the recursive solution.

Answer 2

You can model this problem as a 0/1 Knapsack problem by splitting the $i$-th item $q_i$ times. Let the maximum value in $Q$ be $K$, then the typical 0/1 Knapsack solves the problem in $O(MNK)$ time.

For simplicity, suppose $q_i$ can be written as $1+2+\dots + j$. Then we can split the $i$-th item into new items of price $1\cdot p_i, 2\cdot p_i, \dots , j\cdot p_i$. The powerful thing about this way of splitting is that there is a combination of items to form $1$ to $q_i$. For example, if $q_i=10$ and we split into item {$1, 2, 3, 4\}$, we can form $6$ using $4+2$, $9$ using $4+3+2$ and so on. Therefore, 0/1 Knapsack will still gives a correct answer. If $q_i$ cannot be represented as sum of consecutive natural numbers, find the largest $j$ such that $q_i\geq \sum_{x=1}^j x$ and $r$ be remainder, then split $q_i$ into $\{1,2,\dots ,j, r\}$. Now each item gives $O(\sqrt M)$ more items in the 0/1 Knapsack, hence our solution now becomes $O(MN\sqrt{K})$.

We can further improve this by using the splitting strategy using power of two's $\{1, 2, 4, 8,\dots\}$. Then each item know gives only $O(\lg K)$ new items and our overall solution becomes $O(MN\log K)$.