# Multiple choice knapsack dynamic programming

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.

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.

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