gpt4 book ai didi

javascript - 我想找到最有效的方式来填充车辆,基本上是满足车辆容量的不同组合

转载 作者:搜寻专家 更新时间:2023-11-01 00:47:53 25 4
gpt4 key购买 nike

我正在尝试编写一种算法,根据不同的输入组合将车辆“装满”至其容量。问题已解决,但速度太慢,无法用于更多组合。

例如:我有一辆容量为 10 的车辆,我有不同类型(属性)的座椅组合,可以不同地填充车辆(默认为门诊或正常座椅容量 1)。此外,每个不等于 10 的组合(大于 10 被删除)将被填充为动态容量,或者只是一个普通座位。像这样:

const a = [ {
name: 'wheelchair',
capacity: 0,
total: 3
}, {
name: 'walker',
capacity: 2,
total: 5
}, {
name: 'service animal',
capacity: 2,
total: 5
}];

在上面的例子中还值得注意的是,轮椅每次组合只能添加 3 次,因为它总共有 3(max)。轮椅的 0 容量是此特定属性的指定位置的示例,它不占用任何其他流动座位。

为此,我尝试了几种不同的方法,我的算法对于这个特定的组合运行良好,或者即使我添加了更多。但是,如果我添加一个属性总数为 10 且容量为 1,这将使总可能性增加一个数量级,并极大地减慢算法速度。在我的方法中,我找到了不同的排列,然后过滤掉重复项以找到组合,如果有办法只找到组合,也许它会减少计算量,但我想不出办法。我有一个输出需要查看的特定方式,这是底部的输出,但是,我可以控制输入并且可以在必要时进行更改。非常感谢任何想法或帮助。

此代码是根据此答案修改的 https://stackoverflow.com/a/21640840/6025994


// the power set of [] is [[]]
if(arr.length === 0) {
return [[]];
}

// remove and remember the last element of the array
var lastElement = arr.pop();

// take the powerset of the rest of the array
var restPowerset = powerSet(arr);


// for each set in the power set of arr minus its last element,
// include that set in the powerset of arr both with and without
// the last element of arr
var powerset = [];
for(var i = 0, len = restPowerset.length; i < len; i++) {

var set = restPowerset[i];

// without last element
powerset.push(set);

// with last element
set = set.slice(); // create a new array that's a copy of set
set.push(lastElement);
powerset.push(set);
}

return powerset;
};

var subsetsLessThan = function (arr, number) {
// all subsets of arr
var powerset = powerSet(arr);

// subsets summing less than or equal to number
var subsets = new Set();
for(var i = 0, len = powerset.length; i < len; i++) {

var subset = powerset[i];

var sum = 0;
const newObject = {};
for(var j = 0, len2 = subset.length; j < len2; j++) {
if (newObject[subset[j].name]) {
newObject[subset[j].name]++;
} else {
newObject[subset[j].name] = 1;
}
sum += subset[j].seat;
}
const difference = number - sum;

newObject.ambulatory = difference;

if(sum <= number) {
subsets.add(JSON.stringify(newObject));
}
}

return [...subsets].map(subset => JSON.parse(subset));
};

const a = [{
name: 'grocery',
capacity: 2,
total: 5
}, {
name: 'wheelchair',
capacity: 0,
total: 3
}];
const hrStart = process.hrtime();
const array = [];

for (let i = 0, len = a.length; i < len; i++) {
for (let tot = 0, len2 = a[i].total; tot < len2; tot++) {
array.push({
name: a[i].name,
seat: a[i].capacity
});
}
}
const combinations = subsetsLessThan(array, 10);
const hrEnd = process.hrtime(hrStart);
// for (const combination of combinations) {
// console.log(combination);
// }

console.info('Execution time (hr): %ds %dms', hrEnd[0], hrEnd[1] / 1000000)

预期结果都是传入小于车辆容量的结果组合,本质上是一种组合小于和算法。例如,我发布的代码的预期结果是 -->

[{"ambulatory":10},{"wheelchair":1,"ambulatory":10},{"wheelchair":2,"ambulatory":10},{"wheelchair":3, “门诊”:10},{“杂货店”:1,“门诊”:8},{“杂货店”:1,“轮椅”:1,“门诊”:8},{“杂货店”:1,“轮椅” ":2,"ambulatory":8},{"grocery":1,"wheelchair":3,"ambulatory":8},{"grocery":2,"ambulatory":6},{"grocery": 2,"wheelchair":1,"ambulatory":6},{"grocery":2,"wheelchair":2,"ambulatory":6},{"grocery":2,"wheelchair":3,"ambulatory ":6},{"grocery":3,"ambulatory":4},{"grocery":3,"wheelchair":1,"ambulatory":4},{"grocery":3,"wheelchair": 2,“门诊”:4},{“杂货店”:3,“轮椅”:3,“门诊”:4},{“杂货店”:4,“门诊”:2},{“杂货店”:4, “轮椅”:1,“门诊”:2},{“杂货店”:4,“轮椅”:2,“门诊”:2},{“杂货店”:4,“轮椅”:3,“门诊”: 2},{"grocery":5,"ambulatory":0},{"grocery":5,"wheelchair":1,"ambulatory":0},{"grocery":5,"wheelchair":2, "ambulatory":0},{"grocery":5,"wheelchair":3,"ambulatory":0}]

最佳答案

您可以使用一种技巧来改进您的算法,称为 backtracking :如果你到达一条不可能的路,例如5 -> 6,那你就不用继续找了,因为5+6已经大于10了,这样可以消去很多组合。

   function* combineMax([current, ...rest], max, previous = {}) {
// Base Case: if there are no items left to place, end the recursion here
if(!current) {
// If the maximum is reached exactly, then this a valid solution, yield it up
if(!max) yield previous;
return;
}

// if the "max" left is e.g. 8, then the grocery with "seat" being 2 can only fit in 4 times at max, therefore loop from 0 to 4
for(let amount = 0; (!current.seat || amount <= max / current.seat) && amount <= current.total; amount++) {
// The recursive call
yield* combineMax(
rest, // exclude the current item as that was used already
max - amount * current.seat, // e.g. max was 10, we take "seat: 2" 3 times, then the max left is "10 - 2 * 3"
{ ...previous, [current.name]: amount } // add the current amount
);
}
}

const result = [...combineMax([
{ name: 'grocery', seat: 2, total: Infinity },
{ name: 'wheelchair', seat: 0, total: 3 },
{ name: 'ambulatory equipment', seat: 1, total: Infinity },
//...
], 10)];

关于javascript - 我想找到最有效的方式来填充车辆,基本上是满足车辆容量的不同组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56703395/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com