需要帮助获得尽可能多的独特啤酒
需要帮助获得尽可能多的独特啤酒
提问于 2017-05-19 04:23:32
假设我有一家酒吧，汽车在去海滩之前会停下来买啤酒。每辆车都有一个后备箱大小(remainingSum)，每个啤酒都有一个大小(beer.size)
我想为客户提供他们的汽车后备箱可以容纳的啤酒组合选择(AllCombinations)，但独特的组合。
例如，输入：
let Beers = [
{id: 1, size: 4},
{id: 5, size: 1},
{id: 10, size: 0.5},
{id: 11, size: 1},
{id: 12, size: 2},
{id: 13, size: 1},
];
let TrunkSize = 2;预期输出
AllCombinations = [ // no duplicates
[{id: 5, size: 1}, {id: 10, size: 0.5}],
[{id: 5, size: 1}, {id: 11, size: 1}],
[{id: 5, size: 1}, {id: 13, size: 1}],
[{id: 10, size: 0.5}, {id: 11, size: 1}],
[{id: 10, size: 0.5}, {id: 13, size: 1}],
[{id: 11, size: 1}, {id: 13, size: 1}],
[{id: 5, size: 1}],
[{id: 11, size: 1}],
[{id: 12, size: 2}],
[{id: 13, size: 1}],
[{id: 10, size: 0.5}],
] 电流输出
AllCombinations = [
[{id: 5, size: 1}, {id: 10, size: 0.5}], // dup a
[{id: 5, size: 1}, {id: 11, size: 1}], // dup c
[{id: 5, size: 1}, {id: 13, size: 1}], // dup d
[{id: 10, size: 0.5}, {id: 5, size: 1}], // dup a
[{id: 10, size: 0.5}, {id: 11, size: 1}], // dup b
[{id: 10, size: 0.5}, {id: 13, size: 1}], // dup e
[{id: 11, size: 1}, {id: 13, size: 1}], // dup f
[{id: 11, size: 1}, {id: 10, size: 0.5}], // dup b
[{id: 11, size: 1}, {id: 5, size: 1}], // dup c
[{id: 13, size: 1}, {id: 5, size: 1}], // dup d
[{id: 13, size: 1}, {id: 10, size: 0.5}], // dup e
[{id: 13, size: 1}, {id: 11, size: 1}], // dup f
[{id: 5, size: 1}],
[{id: 11, size: 1}],
[{id: 12, size: 2}],
[{id: 13, size: 1}],
[{id: 10, size: 0.5}]
]当前函数：
AllCombinations = [];
GetCombinations(currentCombination, beers, remainingSum)
{
if (remainingSum < 0)
return;// Sum is too large; terminate recursion
else {
if (currentCombination.length > 0)
{
currentCombination.sort();
var uniquePermutation = true;
for (var i = 0; i < this.AllCombinations.length; i++)
{
if (currentCombination.length == this.AllCombinations[i].length)
{
for (var j = 0; currentCombination[j] == this.AllCombinations[i][j] && j < this.AllCombinations[i].length; j++); // Pass
if (j == currentCombination.length) {
uniquePermutation = false;
break;
}
}
}
if (uniquePermutation)
this.AllCombinations.push(currentCombination);
}
}
for (var i = 0; i < beers.length; i++) {
var newChoices = beers.slice();
var newCombination = currentCombination.concat(newChoices.splice(i, 1));
var newRemainingSum = remainingSum - beers[i].size;
this.GetCombinations(newCombination, newChoices, newRemainingSum);
}
}Stack Overflow用户
发布于 2017-05-19 05:12:35
要获得所有可能的组合而不重复，您可以用一组N位来表示您的组合，其中N=# of?。
因此，您应该得到一个如下所示的表：
000000
000001
000010
000011
000100
000101
000110
000111
...
1111111会告诉您哪些啤酒是可能组合中的一部分。然后你只需将它们的大小相加即可。如果得到的和大于trunkCapacity，则中止循环。
在循环之后，检查该组合的总大小是否在限制范围内，并将其添加到组合列表中。
function getCombination(beers, trunkSize) {
const beersCount = beers.length;
const combinationsCount = Math.pow(2, beersCount);
const combinations = [];
let i = 0; // Change this to 1 to remove the empty combination that will always be there.
while(i < combinationsCount) {
const binary = i.toString(2);
const bits = Array.prototype.concat.apply(Array(beersCount - binary.length).fill(0), binary.split('').map(parseInt));
const combination = [];
let bit = 0;
let total = 0;
while(bit < beersCount && total <= trunkSize) {
if (bits[bit]) {
const beer = beers[bit];
total += beer.size;
combination.push(beer);
}
++bit;
}
if (total <= trunkSize) {
combinations.push(combination)
}
++i;
}
return combinations;
}
const combinations = getCombination([
{id: 1, size: 4},
{id: 5, size: 1},
{id: 10, size: 0.5},
{id: 11, size: 1},
{id: 12, size: 2},
{id: 13, size: 1},
], 2);
console.log(JSON.stringify(combinations, null, 2));
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44057150
复制相关文章
相似问题
腾讯云开发者
