Javascript Algorithm to find the best combination(least number of items) of lengths less than a given value

Question

How to find the best combination of n values which gives the least amount of sum ( n1+n2+n3+n4+n5)

maxDiff = D
requiredLength = L

lengthArray = [l1, l2, l3, l4, l5, l6]

1st constraint,
diff = L - (n1*l1 + n2*l2 + n3*l3 + n4*l4 + n5*l5)

2nd constraint,
0 >= diff <= D

Here, l are different length values of sheets ( 1000mm, 1100mm, ..., 2000mm etc) L is the maximum length required (entered by an user). i want to calculate the best combination of n values(>=0) which basically returns the least number of sheets.

if there is a diff, this can be the gap between sheets. (it can also be 0)

Answer 1

You can find solution with dynamic programming

Make array A of size L+1 containing item counters (initially 0) and the last item added.

For every item length li walk through array from index range k: from A[i] to A[l]

If adding item li to A[k-li] makes count in the cell A[k] better (lower), replace current value in A[k]. Pseudocode:

if (A[k-l[i]].count + 1 < A[k].count) 
   {
     A[k].count = A[k-l[i]].count + 1; 
     A[k].item =  l[i];
   }

Finally check if A[L] contains item set. If now, walk down to get closest result.

To retrieve items, go down by A[k].item steps