meilleur algorithme de combinaison de données complexes avec de multiples contraintes

.as-console-wrapper { max-height: 100% !important; top: 0; }

function getItems(array, constraints, [optimum, equal]) {
    function iter(index = 0, right = [], add) {

        function update() {
            if (!result.length || optimum(right, result[0])) return result = [right];
            if (equal(right, result[0])) result.push(right);
        }

        if (index >= array.length || !constraints.every(fn => fn(right))) return;
        if (add && right.length) update();

        var temp = right.find(({ ref }) => ref === array[index]),
            old = JSON.parse(JSON.stringify(right));

        if (temp) {
            temp.count++;
        } else {
            right.push({ count: 1, ref: array[index] });
        }

        iter(index, right, true);
        iter(index + 1, old);
    }

    var result = [];
    iter();
    return result;
}

const
    addBy = k => (s, { count, ref: { [k]: value } }) => s + count * value,
    addCount = (s, { count }) => s + count;

// find subset of items that minimize cost, hours and peoples
// and maximize number of items
// do not exceed max values!!!
var items = [{ name: "Rome", cost: 1000, hours: 5, peoples: 5 }, { name: "Venice", cost: 200, hours: 1, peoples: 10 }, { name: "Torin", cost: 500, hours: 3, peoples: 2 }, { name: "Genova", cost: 700, hours: 7, peoples: 8 }],
    maxCost = 10000,
    maxHours = 100,
    maxPeoples = 50,
    result = getItems(
        items,
        [
            array => array.reduce(addBy('cost'), 0) <= maxCost,
            array => array.reduce(addBy('hours'), 0) <= maxHours,
            array => array.reduce(addBy('peoples'), 0) <= maxPeoples
        ],
        [
            (a, b) => a.reduce(addCount, 0) > b.reduce(addCount, 0),
            (a, b) => a.reduce(addCount, 0) === b.reduce(addCount, 0)
        ]
    );

console.log(result);

/**
 * Brute Force approach
 * Problem: find combination of data objects to minimize sum of object properties and maximize number of objects
 * Costraint: sum of object properties has upper limit (for each property)
 * Solution used: do every combination, starting with the max number of objects, then lower by 1 each time, until a (or more) combination satisfy every criteria.
 */


// combination
// e.g. combination of 3 numbers with value from 0 to 4 -> combination(3,5)
// see https://rosettacode.org/wiki/Combinations#JavaScript
function combination(n, length) {
 
  // n -> [a] -> [[a]]
  function comb(n, lst) {
if (!n) return [[]];
if (!lst.length) return [];
 
var x = lst[0],
  xs = lst.slice(1);
 
return comb(n - 1, xs).map(function (t) {
  return [x].concat(t);
}).concat(comb(n, xs));
  }
 
  // f -> f
  function memoized(fn) {
m = {};
return function (x) {
  var args = [].slice.call(arguments),
    strKey = args.join('-');
 
  v = m[strKey];
  if ('u' === (typeof v)[0])
    m[strKey] = v = fn.apply(null, args);
  return v;
}
  }
 
  // [m..n]
  function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
  return m + i;
});
  }
 
  var fnMemoized = memoized(comb),
lstRange = range(0, length-1);
 
  return fnMemoized(n, lstRange)
}




// just some math calculation ------
// obviously n & r in N; r < n
function _factor(n){
var f = 1;
while (n > 1){ f *= n--; }
return f;
}
function _factor2(n,to){
var f = 1;
while (n > 1 && n >= to){ f *= n--; }
return f;
}
function _factorFraction(sup,inf){
return (sup > inf) ? _factor2(sup,inf+1) : 1/_factor2(inf,sup+1)
}
function _combination(n,r){
return (r > n/2) ? _factorFraction(n,r)/_factor(n-r) : _factorFraction(n,n-r)/_factor(r); // namely _factor(n)/_factor(n-r)/_factor(r)
}
// just some math calculation ------



var minr = 2,			// set inferior limit (r) of combination search. 2 <= minr < datas.length
datas = [],			// to be set. matrix to be filled with array of data
limits = [0],		// to be set. contains limit for each datas column
comboKeep = [],		// will contain all solutions found
columns,
sums,
timer;
function combineCheck(r){
if (r < minr) return;
console.log("Expected number of combination C(",datas.length,",",r,") = ",_combination(datas.length,r));
var metconditions = 0;
var CNR = combination(r,datas.length);
CNR.forEach(combo => {
	sums = new Array(columns).fill(0);
	// calculate sum for each column
	for (var j=0; j<combo.length; j++){
		for (var i=0; i<columns; i++){
			sums[i] += datas[combo[j]][i];
		};
	}
	// check if conditions are met
	for (var i=0; i<columns; i++){
		if (sums[i] > limits[i]){
			//console.log("sum of column",i,"exceeds limit (",sums[i]," > ",limits[i],")");
			return;
		}
	};
	comboKeep.push(combo);
	metconditions++;
});
console.log("Condition met in ",metconditions,"combos.");
if (metconditions == CNR.length){
	console.log("No need to go further, all combo have been checked.");
	return;
}
//------------
// OPTIONAL...
//------------
if (metconditions) return; // remove this line if you want all possible combination, even with less objects

combineCheck(r-1); // for delayed call: setTimeout( () => combineCheck(r-1), 250 );
}

function combineCheckStarter(){
comboKeep = [];
columns = datas[0].length;
timer = Date.now();
combineCheck(datas.length-1);
timer = Date.now() - timer;
}


//-----------------------------------------
var items = [
{name: "Rome", cost: 1000, hours: 5, peoples: 5},
{name: "Venice", cost: 200, hours:  1, peoples: 10},
{name: "Torin", cost: 500, hours: 3, peoples: 2},
{name: "Genova", cost: 700, hours: 7, peoples: 8},
{name: "Rome2", cost: 1020, hours: 5, peoples: 6},
{name: "Venice2", cost: 220, hours:  1, peoples: 10},
{name: "Torin2", cost: 520, hours: 3, peoples: 2},
{name: "Genova2", cost: 720, hours: 7, peoples: 4},
{name: "Rome3", cost: 1050, hours: 5, peoples: 5},
{name: "Venice3", cost: 250, hours:  1, peoples: 8},
{name: "Torin3", cost: 550, hours: 3, peoples: 8},
{name: "Genova3", cost: 750, hours: 7, peoples: 8}
];
var datas = Array.from(items, e => [e.cost, e.hours, e.peoples]);
var limits = [2500, 8, 20];
//-----------------------------------------

// test ;)
combineCheckStarter();
console.log("Combination found in ",timer,"ms:",comboKeep);


// pretty print results
var prettier = new Array(comboKeep.length),
unifier = new Array(columns).fill(0);
comboKeep.forEach( (combo, k) => {
var answer = new Array(combo.length);
sums = new Array(columns).fill(0);
combo.forEach((itm,i) => {
	answer[i] = items[itm].name;
	for (var j=0; j<columns; j++){
		sums[j] += datas[itm][j];
	};
});
prettier[k] = {items: answer.join(","), cost: sums[0], hours: sums[1], peoples: sums[2]};
for (var j=0; j<columns; j++){
	if (unifier[j]<sums[j]) unifier[j] = sums[j];
};
});
// normalize 
prettier.forEach( e => {
e.total = e.cost/unifier[0] + e.hours/unifier[1] + e.peoples/unifier[2];
});

//find the best (sum of all resource is lower)
prettier.sort( (b,a) => b.total-a.total);
console.log("sorted solutions:",prettier);
console.log("Best solution should be ",prettier[0].items,prettier[0]);