回溯问题 - 不知道该怎么做

Question

我正在尝试制作一个小脚本（对于棋盘游戏，我是 designing:P），它需要一个对象，其中包含 1-4 个英雄攻击伤害的随机对象，以及可能的目标，并计算通过计算每种可能的结果并权衡结果，英雄们在进攻中采取的最佳行动。

这是我的 JavaScript 对象的样子：

var usedAttacks = {
    1: {
      attack: 2,
      attackableMonsters: Array(0, 1, 2)
    },
    2: {
     attack: 1,
     attackableMonsters: Array(0,1,3)
    },
    3:{
     attack: 4,
     attackableMonsters: Array(1,2,3)
    }
}

usedAttacks中的key指向进行攻击的英雄id，attack是英雄可以造成的伤害，attackableMonsters数组是一个数组，包含英雄可以攻击的怪物的 ID。

我想做的是测试给定场景的每个结果，并在每个测试结束时 return 一个 power 值，最后，select 导致最少 power ammount 的场景。

Hero 1 -> Monster 0, Hero 2 -> Monster 0, Hero 3 -> Monster 1 = Power 10
Hero 1 -> Monster 0, Hero 2 -> Monster 0, Hero 3 -> Monster 2 = Power 11
Hero 1 -> Monster 0, Hero 2 -> Monster 0, Hero 3 -> Monster 3 = Power 8
Hero 1 -> Monster 0, Hero 2 -> Monster 1, Hero 3 -> Monster 1 = Power 10
...

根据英雄攻击阶段结束时存活的怪物的攻击力计算威力。

我觉得这个问题一定可以通过一些基本的回溯来解决，但我只是想不出如何在 javascript 中开始解决它。我不需要完整的解决方案，如果有人可以提供一些基本的指导，让我可以开始开发自己的解决方案，我将不胜感激！

Answer 1

可能是这样的：

我们需要一个数组，其中包含我们将使用索引访问的所有怪物 ID：

var monsters = [ /* all the monster IDs*/ ];

然后我们用英雄键和怪物值初始化一个 target 对象：

var target = {};
var numHeroes = 0;
for ( var i in usedAttacks )
    numHeroes++,
    target[i] = 0; // monsters array index.

并用第一个解初始化最佳解：

var minPower     = calcPower( target ),
    bestSolution = clone( target ); // store a copy, we don't want the solution changed.

function clone(obj) { return JSON.parse( JSON.stringify(obj) ); }

然后我们遍历所有怪物和英雄的组合：

for ( var k = 1; i < monsters.length * numHeroes; k++) {

然后我们增加怪物，类似于带进位的增量：

    for ( var i in usedAttacks )                    // iterate hero IDs
        if ( target[i] + 1 >= monsters.length )
            target[i] = 0;                          // wrap around: carry (no break)
        else {
            target[i]++                             // no wrap:
            break;                                  //   abort.
        }

我们与最佳解决方案进行比较并可能更新：

    var p = calcPower( target );
    if ( p < minPower ) {
        minPower = p;
        bestSolution = clone( target );
    }
}

回溯问题 - 不知道该怎么做

Backtracking issue - can't figure out how to do this

javascript

backtracking