PROBLEMA: el siguiente algoritmo recorre una serie de objetos y asigna los objetos a tres subconjuntos de modo que la suma de cada subconjunto es muy cercana (algoritmo codicioso). Si ejecuta el código, notará que en el primer subconjunto p:11 aparece dos veces y en el tercer subconjunto p:10 aparece dos veces. No quiero que el valor p aparezca en la misma matriz más de una vez.
PREGUNTA: ¿Cómo puedo asegurarme en el algoritmo de que el valor de p no aparece en la misma matriz de subconjuntos más de una vez a medida que los objetos se distribuyen a las matrices de subconjuntos mientras me aseguro de que la suma de cada matriz de subconjuntos sigue siendo la misma?
let list = [ {p:2, size:50},{p:4, size:50},{p:5,size:25}, {p:6, size:167},{p:6, size:167},{p:7, size:50}, {p:8, size:25},{p:8, size:50},{p:10, size:75}, {p:10, size:75},{p:11, size:25},{p:11, size:50}, {p:12, size:25},{p:13, size:50},{p:14,size:25} ] function balance_load(power_load_array, number_of_phases) { const sorted = power_load_array.sort((a, b) => b.size - a.size); // sort descending const output = [...Array(number_of_phases)].map((x) => { return { sum: 0, elements: [], }; }); for (const item of sorted) { const chosen_subset = output.sort((a, b) => a.sum - b.sum)[0]; chosen_subset.elements.push({p:item.p, size:item.size}); chosen_subset.sum += item.size; } return output } let p = balance_load(list,3) console.log(p)Esto se puede resolver como un problema de optimización lineal entero con una variable continua, t , y una variable para cada combinación de elementos de list , i y grupo, j :
1 si el elemento i de la list se asigna al grupo j , de lo contrario es igual a 0 .Nos dan los siguientes coeficientes.
c i : costo del elemento i de la list ( list[i][:size] )
p i : valor de p para el elemento i de la list ( list[i][:p] )
S : conjunto de valores únicos list[i][:p] que son compartidos por dos o más elementos de list .
U(s) : conjunto de elementos i de list para los cuales list[i][:p] == s , para cada s en S
La formulación es la siguiente.
(1) t min
sujeto a:
(2) t >= ∑ i x ij c ij para cada j
(3) ∑ j x ij = 1 para cada i
(4) ∑ U(s) x ij <= 1 para cada j y s en S
(5) x ij es igual a 0 o 1 para todos los pares i,j
list se asigne exactamente a un grupolist que tengan el mismo valor de list[:p] .