使用约 25 个物品池中的 6 件物品计算可达到的最高可能伤害

发布于 2024-11-03 15:40:20 字数 1154 浏览 0 评论 0原文

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

问题：

如何获得 6 个项目的所有不同组合的列表？会有多少种组合？只是 25c6 (~134k) 吗？或者我需要删除重复项？（抱歉，我已经离开数学课有一段时间了。）
你会如何在 Javascript 中实现这样的东西？是否已经有一个数学库可以做到这一点？（具体来说，迭代所有可能的项目组合。）
是否可以暴力计算所有可能组合的伤害并保存最重要的物品组合？如果没有，是否有更好的算法来找到强组合？

这是我的代码，基于大家的输入：

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);
});

原文

I am writing an app in javascript to try to figure out item builds for characters in a video game. There are about 25 top-tier items, and you can carry 6 at a time. They have very different effects, which leads me to believe that while one item may seem like it isn't very good by itself, it can become much stronger when combined with others. I can elaborate on that if there is interest.

Questions:

How can I get a list of all the different distinct combinations of 6 items? How many combinations will there be? Is it just 25c6 (~134k)? Or do I need to remove duplicates? (Sorry, I've been out of math class awhile.)
How would you implement something like this in Javascript? Is there already a math library that can do this? (Specifically, iterate through all of the possible combinations of items.)
Does it seem possible to brute force calculate the damage of all the possible combinations and save the top item combinations? If not, is there a better algorithm to find strong combinations?

Here's my code, based on everyone's input:

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);
});

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

云淡风轻 2024-11-10 15:40:20

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 中无法使用。其他选项（例如“本地搜索技术”）似乎不适合您，因为您的空间不是特别连续。

1) Yes, it is just 25 choose 6

2) Well, if you only have to do this once, you can do it with nested loops. The key is to have each of the inner loops not start from zero, but from the outer counter.

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);
    }
}

If you need a generic solution for generic values of 25 and 6 it shouldn't be hard to write a recursive function with similar effects.

3) I think your only option is brute force. It may take a few minutes, but it should complete. I think it will be fastest in Chrome and unusable in IE. Other options like "local search techniques" don't seem like they would work for you because your space is not particularly continuous.

回复收藏 0 原文

森末i 2024-11-10 15:40:20

是的，它是 25C6（实际上约为 177k）
是的重复项，例如。列出 1...n 之间 k 个整数的所有可能组合（n 选择 k）和如何迭代 n 张扑克牌的每种可能组合。
如果您知道只有 6 个项目，则可以只使用 6 个嵌套的 for 循环（尽管这显然不能很好地扩展）。
当然这是可能的 - 在典型的 PC 上迭代 177k 个组合只需不到一秒的时间（可能会长一点，因为您使用的是 Javascript，但不会超过一两秒）

回复收藏 0 原文

作死小能手 2024-11-10 15:40:20

肖恩，

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

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

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

我认为你没有理由不应该在 JavaScript 中实现这个，但我想你必须实现你自己的优先级队列，这本身就非常棘手......好消息是它是一个已发布的数据 -结构，所以我会从 Wikipedia 开始了解它，然后用 google 努力看看我是否能找到一个“像样的”javascript 实现......或者失败，我只是移植 Java 的实现。

这是一个具有挑战性的小问题。我很想看看您的想法以及其他人的建议。让我更新，好吗？

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

干杯。基思.

回复收藏 0 原文

~没有更多了~