javascript - 找到可重复以适应最大总值的一组值的算法
问题描述
我有一套价值观。(它的长度可以是动态的。有些值可以是未定义的)。这些值中的每一个都是一种攻击类型。
前任: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
}]
所以这里的攻击是可能的攻击组合,可以在给定的能量限制和剩余的能量浪费量内完成。因此该函数将有一个名为wastage 的参数,该参数将提及可以完成的最大浪费量。各种类型的攻击可以重复多次。但是消耗的总能量应该小于总能量。
理想情况下,高级攻击的数量是首选的,就像成本更高的攻击一样,但这取决于玩家的决定。所以我将返回所有可能的组合。玩家必须选择物有所值的最佳收益。
我知道这是某种背包问题,但我尝试了多种解决方案,但没有什么能完全解决这个问题。
我通常希望这个解决方案使用 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);
在这里,我得到了一个数组列表,其中包含给定总值的最大攻击组合,现在我该如何从这里开始实施背包呢?
解决方案
背包在这里并不真正相关,因为您想要所有选择。这更类似于将一组数字划分为总和 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);
推荐阅读
- python - 在哪里可以找到 python .difference() 源代码?
- typescript - 仅当不为空时才将变量从数字转换为字符串,否则保留为空
- php - 如何将变量从函数传递到 PHP / Laravel 中的条带化 webhook 函数?
- javascript - 使用ajax添加数据后dataTable的行消失
- pandas - 如何从看起来像 Pandas 中的字典的列中提取数据?
- c - 一起使用二进制信号量和互斥量
- facebook-graph-api - 获取 facebook 帐户账单信息的 API
- ios - 为什么网络库无法检测到互联网何时在 Swift Ios 中重新连接
- node.js - nodejs spotify web api无法使用access_token进行身份验证
- dataset - 如何识别表示整个数据集的数据集子集?