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 &gt;=cuisenaire[n] and n&gt;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]).