Cómo encontrar la mejor combinación de n valores que da la menor cantidad de suma ( 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
Aquí, l
son diferentes valores de longitud de las hojas (1000 mm, 1100 mm, ..., 2000 mm, etc.) L
es la longitud máxima requerida (ingresada por un usuario). quiero calcular la mejor combinación de n
valores (> = 0) que básicamente devuelve la menor cantidad de hojas.
si hay una diferencia, puede ser el espacio entre las hojas. (también puede ser 0)
Puedes encontrar la solución con programación dinámica.
Cree una matriz A
de tamaño L+1
que contenga contadores de elementos (inicialmente 0) y el último elemento agregado.
Para cada longitud de elemento, li
la matriz desde el rango de índice k
: de A[i] to A[l]
Si agregar el elemento li
a A[k-li]
hace que el recuento en la celda A[k]
sea mejor (más bajo), reemplace el valor actual en A[k]
. Pseudocódigo:
if (A[kl[i]].count + 1 < A[k].count) { A[k].count = A[kl[i]].count + 1; A[k].item = l[i]; }
Finalmente, compruebe si A[L]
contiene un conjunto de elementos. Si ahora, camine hacia abajo para obtener el resultado más cercano.
Para recuperar elementos, baje los pasos A[k].item