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