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;

-
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

-
can't think on recursive idea

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

StackExchange Computer Science Q#68705, answer score: 2