用于查找可重复的值集以拟合最大总值的算法

Question

我有一组值。(它的长度可以是动态的，有些值可以是未定义的(。其中每个值都是一种攻击类型。

例如：attacks=[960,1200,1800,2120,undefined,undefined];

和总价值，

例如：totalEnergy=18680;

现在我想要一个函数来返回一个对象数组，例如，

前任：

[{
attacks: [0,0,0,0,1,2],
wastage: 128
}, {
attacks: [0,1,2,2,2],
wastage: 298
}, {
attacks: [2,3,4],
wastage: 593
}]

因此，这里的攻击是可以在给定的能量限制和剩余能量浪费量内完成的可能的攻击组合。 因此，该函数将具有一个名为浪费的参数，该参数将提及可以完成的最大浪费量。 各种类型的攻击可以重复多次。但消耗的总能量应该小于总能量。

理想情况下，首选更高级别的攻击数量，例如成本更高的攻击，但这取决于玩家的决定。所以我将返回所有可能的组合。玩家必须选择最好的爆炸物

。我知道这是某种背包问题，但我尝试了多种解决方案，但没有一个能完全解决这个问题。

我通常希望这个解决方案是javascript，但任何语言都可以用于演示目的。

更新：

这是我到目前为止得到的，

let totalEnergy = 3400;
let attacks = [980, 1220, 1680, 1920];
let attacksPossible = attacks.map((attack, iter) => {
return Math.floor(totalEnergy/attack);
})
// Create an array which contains a repeatitive number of attacks possible
let attacksArray = attacks.map((attack, iter) => {
return [...Array(attacksPossible[iter])].map(() => attack)
})
// Flatten 2D array into 1D array
attacksArray = [].concat.apply([], attacksArray);
console.log('attacksPossible', attacksPossible);
console.log('attacksArray', attacksArray);

在这里，我得到了一个数组列表，其中包含给定总值的最大攻击组合，现在我如何从这里开始在其上实现背包？

Answer 1

背包在这里并不真正相关，因为您想要所有选择。这更类似于将一组数字划分为求和 n 的所有方法，除了您可能会浪费。方法相同，但稍作修改：

let totalEnergy = 3400;
let attacks = [980, 1220, 1680, 1920];
let possibilities = [];
let current = [];
let minVal = Math.min.apply(null, attacks);
function solve (idx, left) {
for (var i = idx; i < attacks.length;i++) {
if (attacks[i] != undefined && attacks[i] <= left) {
current.push(i);
solve(i, left - attacks[i]);
current.pop();
}
}

if (left < minVal) {
possibilities.push({attacks: current.slice(0), waste: left})
} 
}
solve(0, totalEnergy);
console.log(possibilities);