2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.