多约束条件下复杂数据的最佳组合算法
best combination algorithm of complex data with multiple contraints
我想我们可以说这与此处已经提出的问题 (Optimisation/knapsack algorithm with multiple contraints in JavaScript) 非常相似，但还没有答案。
假设我们喜欢 javascript、C、C++、java。这些语言中的任何一种都适合我。有人知道解决问题的算法吗？
问题：
在知道存在资源限制的情况下找到授予最低成本和最大对象数量的最佳项目子集：
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 maxCost = 10000, maxHours = 100, maxPeoples = 50;
// find subset of items that minimize cost, hours and peoples
// and maximize number of items
// do not exceed max values!!!
我的想法：我想我可以为每对成本做一个背包问题的解决方案（我们称它们为 "KPcost-hours"、"KPhours-cost"、"KPcost-peoples" 等），其中授予我优化单一成本的解决方案。然后，如果我幸运的话，获取这个子集的公共部分并从那里开始工作……但我认为这不是一条好路子……
如果能给个脚本示例，或者伪脚本示例，不客气！谢谢！
通过检查所有组合的蛮力方法。
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);
.as-console-wrapper { max-height: 100% !important; top: 0; }
一般解
PROBLEM: find the best subset of items which grants minimum cost and
maximum number of objects, knowing that there's a limitation of
resource.
我在这里看到两个优化标准（我将在下面讨论您希望最大限度地减少人员、时间和成本的情况）。
一种可能的方法是构建一个最多 return Pareto-optimal set of solutions 的程序。
帕累托集是一组非支配解，意味着对于任意两个解S1和S2，S1不支配S2，并且反之亦然。如果解决方案 S1 在所有标准方面优于或等于 S2，并且在至少一个标准方面严格优于解决方案 S2。
比如你的情况，我们可以考虑以下解决方案：
S1: cost = 10, nb_objects = 4
S2: cost = 10, nb_objects = 7
S3: cost = 0, nb_objects = 0
S4: cost = 14, nb_objects = 6
那么我们的帕累托最优解集就是{S1, S3, S4}。那是因为它们不相互支配（例如，S1 不支配 S4，因为 S4 在对象数量方面更好）。 S2 不是 Pareto 最优解的一部分，因为它同时受 S1 和 S4 支配。
在一般情况下，Pareto-set 很难计算，而且可能非常大。在您的特定情况下，4 个标准似乎在某种程度上是合理的，但它总是令人惊讶。
下面是关于如何计算这样一组解的伪代码：
Result = array of size nb_objects, initialized with empty sets
for i from 0 to total_nb_of_objects:
for each feasible solution 'new_solution' to the problem with fixed number of objects:
for each solution of Result[i]:
if hours(new_solution) >= hours(solution) and \
cost(new_solution) >= cost(solution) and \
people(new_solution) >= people(solution):
dominated = true
break
if not dominated:
add new_solution to Result[i]
return Result
这里的这个小伪代码对于尝试和理解帕累托效率的概念更有价值，我不建议循环所有可行的背包问题变体解决方案（成本太高）。
假设每个项目只能 select 0 或 1，则有 2^12=4096 种可能的组合。可行解数为3473，非支配（或帕累托最优）解数为83。
我使用了两种不同的方法：
列举所有可行解。然后过滤掉所有占主导地位的解决方案（每个解决方案必须至少有一个 objective 优于所有其他解决方案）。
写一个混合整数规划。它找到了一个解决方案，并添加了一个约束条件：它应该至少在 objective 中的一个比以前的解决方案更好。 （按照 model 的思路）。
两种方法都找到了这 83 个解决方案。对于这个问题，完全枚举更快。
请注意，帕累托最优解的数量可能会快速增长。 Here 是真实世界设计问题的帕累托最优集的一些图片。
请注意，没有 "single" 最佳解决方案。所有帕累托最优解都是最优的。只有当你对 objective 之间的权衡做出假设时，你才能进一步减少最优解的数量。
我详细阐述了一个可行的解决方案，但它确实是蛮力的，但有点优化。我没有通过 Pareto 解决方案，我认为它可能是更好的解决方案。不幸的是，Nina Sholz 的脚本不起作用（至少对我而言），所以我想到了这个。
只是在这里留下一个工作示例（阅读：不要用于大数据）。
PS - 如果有人能用更好的英语写任何短语，请在下面评论，我会改正我的错误。
/**
* 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]);
我想我们可以说这与此处已经提出的问题 (Optimisation/knapsack algorithm with multiple contraints in JavaScript) 非常相似，但还没有答案。
假设我们喜欢 javascript、C、C++、java。这些语言中的任何一种都适合我。有人知道解决问题的算法吗？
问题： 在知道存在资源限制的情况下找到授予最低成本和最大对象数量的最佳项目子集：
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 maxCost = 10000, maxHours = 100, maxPeoples = 50;
// find subset of items that minimize cost, hours and peoples
// and maximize number of items
// do not exceed max values!!!
我的想法：我想我可以为每对成本做一个背包问题的解决方案（我们称它们为 "KPcost-hours"、"KPhours-cost"、"KPcost-peoples" 等），其中授予我优化单一成本的解决方案。然后，如果我幸运的话，获取这个子集的公共部分并从那里开始工作……但我认为这不是一条好路子……
如果能给个脚本示例，或者伪脚本示例，不客气！谢谢！
通过检查所有组合的蛮力方法。
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);
.as-console-wrapper { max-height: 100% !important; top: 0; }
一般解
PROBLEM: find the best subset of items which grants minimum cost and maximum number of objects, knowing that there's a limitation of resource.
我在这里看到两个优化标准（我将在下面讨论您希望最大限度地减少人员、时间和成本的情况）。
一种可能的方法是构建一个最多 return Pareto-optimal set of solutions 的程序。
帕累托集是一组非支配解，意味着对于任意两个解S1和S2，S1不支配S2，并且反之亦然。如果解决方案 S1 在所有标准方面优于或等于 S2，并且在至少一个标准方面严格优于解决方案 S2。
比如你的情况，我们可以考虑以下解决方案：
S1: cost = 10, nb_objects = 4
S2: cost = 10, nb_objects = 7
S3: cost = 0, nb_objects = 0
S4: cost = 14, nb_objects = 6
那么我们的帕累托最优解集就是{S1, S3, S4}。那是因为它们不相互支配（例如，S1 不支配 S4，因为 S4 在对象数量方面更好）。 S2 不是 Pareto 最优解的一部分，因为它同时受 S1 和 S4 支配。
在一般情况下，Pareto-set 很难计算，而且可能非常大。在您的特定情况下，4 个标准似乎在某种程度上是合理的，但它总是令人惊讶。
下面是关于如何计算这样一组解的伪代码：
Result = array of size nb_objects, initialized with empty sets
for i from 0 to total_nb_of_objects:
for each feasible solution 'new_solution' to the problem with fixed number of objects:
for each solution of Result[i]:
if hours(new_solution) >= hours(solution) and \
cost(new_solution) >= cost(solution) and \
people(new_solution) >= people(solution):
dominated = true
break
if not dominated:
add new_solution to Result[i]
return Result
这里的这个小伪代码对于尝试和理解帕累托效率的概念更有价值，我不建议循环所有可行的背包问题变体解决方案（成本太高）。
假设每个项目只能 select 0 或 1，则有 2^12=4096 种可能的组合。可行解数为3473，非支配（或帕累托最优）解数为83。
我使用了两种不同的方法：
列举所有可行解。然后过滤掉所有占主导地位的解决方案（每个解决方案必须至少有一个 objective 优于所有其他解决方案）。
写一个混合整数规划。它找到了一个解决方案，并添加了一个约束条件：它应该至少在 objective 中的一个比以前的解决方案更好。 （按照 model 的思路）。
两种方法都找到了这 83 个解决方案。对于这个问题，完全枚举更快。
请注意，帕累托最优解的数量可能会快速增长。 Here 是真实世界设计问题的帕累托最优集的一些图片。
请注意，没有 "single" 最佳解决方案。所有帕累托最优解都是最优的。只有当你对 objective 之间的权衡做出假设时，你才能进一步减少最优解的数量。
我详细阐述了一个可行的解决方案，但它确实是蛮力的，但有点优化。我没有通过 Pareto 解决方案，我认为它可能是更好的解决方案。不幸的是，Nina Sholz 的脚本不起作用（至少对我而言），所以我想到了这个。
只是在这里留下一个工作示例（阅读：不要用于大数据）。
PS - 如果有人能用更好的英语写任何短语，请在下面评论，我会改正我的错误。
/**
* 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]);