如下demo：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta menuName="viewport" content="wmenuPKth=device-wmenuPKth, initial-scale=1.0">
<title>套餐组合最优价格算法</title>
</head>
<body>
</body>
<script>
// 基础菜单数据
const menu = [
{ menuPK: 1, menuName: '菜品1', menuPrice: 10, menuCount: 1 },
{ menuPK: 2, menuName: '菜品2', menuPrice: 15, menuCount: 1 },
{ menuPK: 3, menuName: '菜品3', menuPrice: 12, menuCount: 1 },
{ menuPK: 4, menuName: '菜品4', menuPrice: 25, menuCount: 1 },
];
const combos = [
{
menuPK: 5,
menuName: '套餐1',
menuPrice: 30,
menuCount:1,
menuGroups: [
{ menuPK: 1, menuCount: 1 },
],
},
{
menuPK: 6,
menuName: '套餐2',
menuPrice: 40,
menuCount:1,
menuGroups: [
{ menuPK: 2, menuCount: 1 },
{ menuPK: 3, menuCount: 1 },
],
},
{
menuPK: 7,
menuName: '套餐3',
menuPrice: 30,
menuCount:1,
menuGroups: [
{ menuPK: 1, menuCount: 1 },
{ menuPK: 2, menuCount: 1 },
{ menuPK: 3, menuCount: 3 },
],
},
];
//现有菜单
let givenmenuGroups = [
{ menuPK: 1, menuCount: 2 ,menuPrice:10},
{ menuPK: 3, menuCount: 4 ,menuPrice:12},
{ menuPK: 2, menuCount: 3 ,menuPrice:15},
{ menuPK: 4, menuCount: 1 ,menuPrice:25}
];
//现有菜品按主键排序
givenmenuGroups = givenmenuGroups.sort((a,b)=>a.menuPK-b.menuPK);
console.log("原始菜单",givenmenuGroups);
console.log("原始套餐总数据",combos);
let tcObj = thaliChange(combos);
console.log("套餐对象",tcObj);
let lastObj={};
console.time("总体耗时:");
let lObj= dishCombination("",givenmenuGroups);
/**
* oldMenu 需要组合的菜品
* finalArray 最终组合完成的集合
* */
function dishCombination(nKey,oldMenu){
const combinations = generateCombinations([...oldMenu]);
const combinationsObj = combinationChangeObject(combinations);
const overCombinations = caclCombination(combinationsObj);
for(let key in overCombinations){
let newMenu = [{...overCombinations[key]}];
let menuGroups = overCombinations[key].menuGroups||[];
//最原始的菜单数据重新计算其他的组合
let copyData = JSON.parse(JSON.stringify(oldMenu));
let keyArr=[];
copyData.map(item=>{
let addState = false;
if(!item.menuGroups){
menuGroups.map(atem=>{
if(item.menuPK===atem.menuPK){
addState=true;
keyArr.push(atem.menuPK);
item.menuCount-=atem.menuCount;
if(item.menuCount>0){
newMenu.push(item)
}
}
});
};
if(!addState){
newMenu.push(item);
};
});
let nameKey = nKey?nKey:keyArr.join("-");
lastObj[nameKey] = newMenu;
}
if(overCombinations&&overCombinations.length){
for(let key in lastObj){
let menuArr = lastObj[key];
dishCombination(key,menuArr);
}
}
}
if(Object.keys(lastObj).length){
console.log("最终计价组合:",lastObj);
let lastArr=[];
for(let key in lastObj){
let menuArray = lastObj[key]||[];
let obj = {totalMoney:0,menuArray};
menuArray.map(item=>{
let count= item.menuCount||1;
obj.totalMoney+=Math.round(item.menuPrice*count);
});
lastArr.push(obj);
}
let newLastArr = lastArr.sort((a,b)=>a.totalMoney-b.totalMoney);
console.log("总体套餐各个优惠价",newLastArr);
let finalResult = newLastArr[0];
console.log("最优套餐组合-",finalResult.menuArray,"总价:"+finalResult.totalMoney);
}else{
console.log("未匹配到套餐使用原菜单:",givenmenuGroups);
}
console.timeEnd("总体耗时:");
//所有套餐组合明细
function thaliChange(thArr){
let tObj={};
thArr.map(item=>{
let menuGroups = item.menuGroups||[];
let dishSort = menuGroups.sort((a,b)=>a.menuPK-b.menuPK);
let keys = [];
dishSort.map(atem=>{
keys.push(atem.menuPK);
});
if(keys.length){
tObj[keys.join("-")] = item;
}
});
return tObj;
};
//菜单中所有组合方法函数
function generateCombinations(arr) {
let genArr = [];
function backtrack(start, currentCombination) {
if(currentCombination.length){
genArr.push([...currentCombination]);
}
for (let i = start; i < arr.length; i++) {
if(arr.menuGroups&&arr.menuGroups.length) continue;
currentCombination.push(arr[i]);
backtrack(i + 1, currentCombination);
currentCombination.pop();
}
}
backtrack(0, []);
genArr = genArr.sort((a,b)=>a.length-b.length);
return genArr;
}
//菜单中的所有组合转换成对象
function combinationChangeObject(csArr){
let combinationsObj={};
csArr.map(item=>{
let key = [];
item.map(atem=>{
key.push(atem.menuPK);
})
combinationsObj[key.join("-")]=item;
});
return combinationsObj;
}
//计算与套餐中匹配到的组合
function caclCombination(combinationsObj={}){
let lastArray = [];
for(let key in combinationsObj){
if(tcObj[key]){ //筛选出匹配到的组合
let menuGroups = tcObj[key].menuGroups;
let cMenu = combinationsObj[key]||[];
let countState = true;
menuGroups.map(item=>{
cMenu.map(atem=>{
if(item.menuPK===atem.menuPK && item.menuCount>atem.menuCount){
countState = false;
}
});
});
if(countState){
lastArray.push(tcObj[key]);
}
}
}
return lastArray;
}
</script>
</html>
