# Version of knap sack problem

The are cuisenaire rods with N differnt lengthes $x_1,x_2,...,x_n$ (each length is a natural number), the number of the Cuisenaire rods is unlimited. Given a natural number B. you should tell if you can pick a bunch of Cuisenaire rods with exactly the length of B.

for example: if the cuisenaire rods are $3,11,19$ and $B=20$ so you should return true because $3+3+3+11=20$. but for $B=19$ return false.

I made a $(N+1)\times(B+1)$ table named "opt", checked for all $0\leqslant i\leqslant n$ and for all $0\leqslant b\leqslant B$ if i can get a length using the lengthes $x_1,x_2,...,x_i$ and weights $0\leqslant b\leqslant B$

For the given example he output should be (this is my output also)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1

My idea:

fill in with zeros the first line and the first column, i.e opt[0][b]=0 for all b and opt[n][0]=0 for all n

Here cuisenaire={0,3,11,19} is array with the cuisenaire lengths

for n=1 to N+1
for b=1 to B
opt[n][b]=opt[n-1][w];//copy the previos row
if w modulu cuisenaire[k]=0
opt[n][w]=1;

if w >=cuisenaire[n] and n>1 and (w+cuisenaire[n]-1)module (cuisenaire[n-1])=0)
opt[n][w]=1;
1. my Idea works only for small B's $\implies$ wrong idea but maybe close, e.g for $B=100$ and cuisenaire={0,13,19,29} my idea doesn't work

2. can't think on recursive idea

• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
Jan 14, 2017 at 17:11
• One has to return false, if B can be made only of a single rod, right? That's the reason we consider rods of length zero, right? Jan 19, 2017 at 17:18
• I see contradiction in the problem statement: it says that rod lengths are natural numbers (so can't be zero) and then shows that set 3, 11, 19 can't made a 19. Further examples show rod of length zero. Please, clarify. Jan 19, 2017 at 17:25
• I too am confused why we should return false for $B=19$. It seems for $B=19$ we should return true, because you can pick a single Cuisenaire rod of length 19 and that will suffice.
– D.W.
Jan 19, 2017 at 19:59

Your question is equivalent to the decision version of the unbounded knapsack optimization problem. The decision is whether the maximum value (after optimization) is equal to the upper bound. Moreover, the weights and values are identical in your question (i.e. the length is both the weight and the value).

# Problem Formulation

The unbounded knapsack optimization problem is as follows:

Given a set of $n$ objects where object $i$ has weight $w_i$ and value $v_i$,

$\>\>$ maximize $\sum_{i=1}^{n} v_i m_i$

$\>\>$ subject to $\sum_{i=1}^{n} w_i m_i \leq W, \\ m_i \in \mathbb{N}$

where $m_i$ denotes the multiplicity of object $i$, and $W$ is some upper bound.

(note that we're using the definition of $\mathbb{N}$ that includes zero here)

The decision version of this problem can be formulated in terms of the optimization version:

Is the maximum value of the unbounded knapsack optimization problem over the given set of objects $(w_i,v_i)^*$ and upper bound $W$ equal to $V$?

Now let's map these descriptions to your particular question. First, note that length of a cuisenaire rod is equal to both its weight and its value. So we can replace every $w_i$ and $v_i$ with just $x_i$. Similarly, the upper bound on the weight is also the target value for the decision problem. So we can replace both $W$ and $V$ with $B$. Finally, since the selection variable $m_i$ is already using the definition of the natural numbers that includes zero, let's be precise and replace every instance of "natural number" in your problem description with "positive integer".

This results in the following problem formulation:

Given some $B$ and a set of $n$ cuisenaire rods of lengths $x_1, x_2, ..., x_n$ where $B \in \mathbb{Z^+} \land \forall x_i (x_i \in \mathbb{Z^+})$,

is the result of maximizing

$\>\>\>\>\>\> \sum_{i=1}^{n} x_i m_i$

subject to

$\>\>\>\>\>\> \sum_{i=1}^{n} x_i m_i \leq B, \\ \>\>\>\>\>\> m_i \in \mathbb{N}$

equal to $B$?

# Solution as Recurrence Relation

Since $\forall x_i(x_i \in \mathbb{Z})$, we can most easily solve this knapsack problem by formulating a recurrence relation for it. So let $M[b]$ denote the maximum length less than or equal to $b$ of an unbounded combination of the given cuisenaire rods. The base case is $M[0] = 0$, since we can always select a combination of zero cuisenaire rods (i.e. set every $m_i$ to $0$) whose sum is the maximum value less than or equal to zero (i.e. zero itself).

The recursive case is formulated in terms of reducing the allowable maximum length by the different cuisenaire rod lengths. The idea is to see whether specifying that we have used one of rod $x_1$, $x_2$, ..., or $x_n$ gets us closer to $B$. In specifying that we have used one of rod $x_i$, we may remove that rod from the tally and recurse on the smaller value, i.e. $M[b-x_i]$. In order to find the maximum value, we add the value of the rod that we just removed to whatever the maximum length of the smaller limit is, i.e. $M[b] = x_i + M[b-x_i]$. More specifically, $M[b]$ is equal to the maximum possible value that we could achieve between selecting one rod from all the different rods, i.e. $M[b] = max_{i=1}^{n} (x_i + M[b-x_i])$.

Note that since this is the unbounded knapsack problem, we cannot say whether we will use the selected rod (or any other rod) again in the solution. In terms of formulating the recurrence relation, all we can say for certain is that the selected rod is used at this specific step. The decision about what rod to select next (or even to select this rod again) is left entirely up to the next step in the recursion.

Putting this all together, and assuming that both $B > 0$ and $\forall x_i (x_i > 0)$ in order to avoid wonky edge cases, we get the following recurrence relation:

$\>\> M[0] = 0, \\ \>\> M[b] = max_{i=1}^{n}(x_i + M[b-x_i])$

Note that $M[b]$ is undefined for any $b < 0$. If we want to be really precise about it, we could express this formally as $M[b] = max_{\{x_i | b-x_i \geq 0\}}(x_i + M[b-x_i])$.

We can now find the maximum length less than or equal to $B$ of any unbounded combination of cuisenaire rods by evaluating $M[B]$. This solves the optimization problem. To solve the decision problem, simply check if $M[B] = B$.

# Dynamic Programming

Since $\forall x_i(x_i \in \mathbb{Z})$, we can easily apply dynamic programming by instantiating an array (with all elements initialized to zero) of length $B$. Store and lookup the value of each term in this recurrence relation in that array.

We can optimize this dynamic programming solution in two main ways. First, we can reduce the runtime by iteratively filling in the array from $M[0]$ to $M[B]$ in order to avoid the function call overhead of recursively starting at $M[B]$.

Second, we can reduce the space by observing that a circular array of size $\mathcal{max_{i=1}^{n}(x_i)}+1$ is sufficient to hold as many previously calculated values as is required to calculate any $M[b]$. This is because for any $b$, in order to calculate $M[b]$ we will only need to look as far "back" in the array as $max_{i=1}^{n}(x_i)$. For example, if $x_1 = 5$ and $x_2 = 7$, then to calculate $M[20]$ we would only need to look at $M[20-5]$ and $M[20-7]$.

Furthermore, if desired, we can also preprocess the set of rods to determine if there is a simpler solution (i.e. check if $\exists x_i (B \> mod \> x_i \equiv 0)$, to remove rods that cannot be part of the solution (i.e. $x_i > B$), to remove redundant rods (i.e. $x_i$ is redundant if $\exists j \neq i (x_j \> mod \> x_i \equiv 0)$), etc.

# Example

Here is a working example in Python (without any of the preprocessing optimizations):

def cuisenaire(B, rods):
"""
B is a positive integer that serves as the targeted upper bound (inclusive).
Rods is a list of cuisenaire rods with positive integer lengths listed
in ascending order.
"""

dp = [0] * (max(rods)+1)  # dynamic programming workspace

for i in range(1,B+1):  # iteratively fill DP workspace (1 to B, inclusive)

for rod in rods:  # evaluate each first-order subproblem

if i - rod >= 0:  # dp[index] undefined for index < 0
temp = rod + dp[(i - rod) % len(dp)]  # the core recurrence relation
if temp > dp[i % len(dp)]:  # if this value is greater than other,
dp[i % len(dp)] = temp  # then update DP cell to greater value
else:
break  # optimization, not required for correctness

return dp[B % len(dp)] == B  # solve the decision problem

The time complexity of this code is $O (B \cdot n)$ which is B * len(rods).

The space complexity of this code is $O (max_{i=1}^{n}(x_i))$ which is max(rods).

• Please, formulate the solution and explanation in terms of specific problem i.e. use $x_i$ and B rather than $v_i$ and W. 0 isn't a natural number. Why circular array is sufficient? What is the meaning of m[w]? Jan 20, 2017 at 6:06
• @ivan_onys Good point. I'll edit the answer for clarity (change variable names, elaborate on array size, explain the recurrence relation in prose) tomorrow. However, 0 can most definitely be a natural number: mathworld.wolfram.com/NaturalNumber.html, and this problem still makes sense if so. That being said, my example code did not correctly handle that case, so I will restrict the problem statement to only allow $\mathbb{Z^+}$ for $w_i$ and $W$ for simplicity. Jan 20, 2017 at 8:14

The problem is similar to coin denomination with infinite number of coins available.

Let me know if this works ... http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

For every length which you encounter, you have two options, you can either use this rod or ignore this rod length and continue to the next one. In both the cases you can check if you could reach the target. If you can return true, else false.

So lets say you have a function canFindTarget( inputArray[], idx , sum ) which returns true if you can make sum using inputArray[0..idx-1] else false. Your answer would be canFindTarget( inputArray[], idx-1, sum ) || canFindTarget( inputArray[], idx, sum - inputArray[idx - 1]).