0

我正在用 javascript 编写一个应用程序，试图找出视频游戏中角色的项目构建。顶级物品大约有 25 件，一次可以携带 6 件。它们有非常不同的效果，这让我相信，虽然一个项目本身看起来不是很好，但与其他项目结合起来会变得更强大。如果有兴趣，我可以详细说明。

问题：

  1. 如何获得 6 个项目的所有不同不同组合的列表？会有多少种组合？它只是 25c6 (~134k) 吗？还是我需要删除重复项？（对不起，我有一段时间没上数学课了。）

  2. 你将如何在 Javascript 中实现这样的东西？是否已经有一个数学库可以做到这一点？（具体来说，遍历所有可能的项目组合。）

  3. 似乎可以蛮力计算所有可能组合的伤害并保存顶级项目组合？如果没有，是否有更好的算法来找到强组合？

这是我的代码，基于每个人的输入：

function getAllCombinations(n, k, callback)
{
    var iterate = function(remaining, args)
    {   
        var len = args.length;
        for (var i = args[len - 1]; i < n; i++)
        {
            args.splice(len);
            args[len - 1] = i;
            if (remaining)
            {
                args.push(i);
                iterate(remaining - 1, args);
            }
            else
            {
                callback.apply(null, args);         
            }
        }        
    }
    iterate(k - 1, [0]);
}

var itemsCount = 25;
var itemSlots = 6;
getAllCombinations(itemsCount, itemSlots, function(a, b, c, d, e, f)
{   
    // calculateDamage(hero, arguments);
});
4

3 回答 3

2

1) 是的，只有 25 选择 6

2）好吧，如果你只需要这样做一次，你可以用嵌套循环来做。关键是让每个内部循环不是从零开始，而是从外部计数器开始。

for (int i = 0; i < 25; i++) {
    for (int j = i; j < 25; j++) { // note j=i not j=0
        // etc
        foo(i,j,k,l,m,n);
    }
}

如果您需要通用值 25 和 6 的通用解决方案，那么编写具有类似效果的递归函数应该不难。

3）我认为你唯一的选择是蛮力。这可能需要几分钟，但应该会完成。我认为它将在 Chrome 中最快，在 IE 中无法使用。其他选项（例如“本地搜索技术”）似乎不适用于您，因为您的空间不是特别连续。

于 2011-04-26T22:51:18.720 回答
1

  1. 是的，它是 25C6（实际上是 ~177k）

  2. 是的副本，例如。列出 1...n (n 选择 k) 之间的 k 个整数的所有可能组合以及如何遍历 n 个扑克牌的所有可能组合。
    如果您知道只有 6 个项目，则可以只使用 6 个嵌套的 for 循环（尽管这显然不能很好地扩展）。

  3. 当然这是可能的——在典型的 PC 上迭代 177k 组合只需要几分之一秒（可能会更长一些，因为您使用的是 Javascript，但不会超过一两秒）

于 2011-04-26T22:56:46.520 回答
1

肖恩，

对我来说，这听起来像是大英博物馆算法的工作……当然还有奶酪。

通过奶酪，我的意思是遍历特定节点（总体优先级）的“成本”（或在您的情况下的“利润”）可能是这个节点的一个函数，它结合了它在这个路径中的所有前辈。遍历任何特定节点将比传统的“迷宫”在计算上昂贵很多，其中每个节点都有固定的遍历成本（例如街道的长度）......但最大路径长度仅为 6您应该能够始终快速（即亚秒级）达到最佳结果的节点。

为避免重复，请不要将节点 A 添加到已经包含节点 A 的路径中。

我看不出你为什么不应该在 javascript 中实现它，但我想你必须实现自己的优先级队列，这本身就很棘手......好消息是它是一个已发布的数据-结构，所以我会从维基百科开始了解它，然后用谷歌搜索我是否能找到一个“体面”的 javascript 实现......或者如果我失败了，我只会移植 Java 的实现。

这是一个具有挑战性的小问题。我很想看看你想出什么，以及其他人在此过程中的建议。让我更新willya？

还有一个建议……通常最好不要让游戏做出最佳决策；因为你的对手“普通人”完全无法在一秒钟内计算出“25 次方中的 6 次”的良好（更不用说最佳）组合，而他们意外获得最佳组合的概率是 25 分之一* 24 * 23 * 22 * 21 * 20 = 127,512,000 ...特别是如果这些“权力”以“秘密”方式相互利用......即使秘密被公布，也需要“程序员的头脑”来做数学，足以达到“高于平均水平”的结果。你明白我的意思吗？

干杯。基思。

于 2011-04-26T23:22:56.673 回答