Where l_1 = 1, l_2 = 4, l_3 = 5 are blocks with different length and I need to make one big block with the length of l = 8 using the formula.
Can someone explain me the following formula:
The formula is in LaTeX, with array L = [l + 1]
Sorry about the formatting, but I can`t upload images.
The question seems to be about finding what is the minimum number of blocks needed to make a bigger block. Also, there seems to be no restriction on the number of individual blocks available.
Assuming you have blocks of n different lengths. l1, l2 .. ln
. What is the minimum number of blocks you can use to make one big block of length k
?
The idea behind the recursive formula is that you can make a block of length i
by adding one block of length l1
to a hypothetical big block of length i-l1
that you might already have made using the minimum number of blocks (because that is what your L
array holds. For any index j
, it holds the minimum number of blocks needed to make a block of size j
). Say the i-l1
block was built using 4 blocks. Using those 4 blocks and 1 more block of size l1
, you created a block of size i
using 5 blocks.
But now, say a block of size i-l2
was made only using 3 blocks. Then you could easily add another block of size l2
to this block of size i-l2
and make a block of size i
using only 4 blocks!
That is the idea behind iterating over all possible block lengths and choosing the minimum of them all (mentioned in the third line of your latex image).
Hope that helps.