Расчет максимально возможного урона, достижимого при использовании 6 предметов из пула ~ 25

Question

Я пишу приложение в 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);
});

Answer 1

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.Другие параметры, такие как «методы локального поиска», похоже, не будут работать на вас, потому что ваше пространство не особенно непрерывно.

Answer 2

Шон,

Для меня это звучит как работа по алгоритму Британского музея ... с сыром, конечно.

Под сыром я подразумеваю, что «стоимость» (или «прибыль» в вашем случае) прохождения определенного узла (общий приоритет) может быть функцией этого узла в сочетании со всеми его предшественниками в этом пути , Обход любого конкретного узла будет ОЧЕНЬ дороже в вычислительном отношении, чем традиционный "лабиринт", где каждый узел имеет фиксированную стоимость обхода (например, длину улицы) ... но с максимальной длиной пути всего шесть узлы, которые вы должны всегда иметь возможность быстро достигать наилучшего результата (то есть менее секунды).

Чтобы избежать дублирования, просто не добавляйте узел A к пути, который уже содержит узел A.

Я не вижу причин, почему вы не должны реализовывать это в javascript, но я полагаю, вам нужно реализовать собственную очередь приоритетов, и это довольно сложно само по себе ... Хорошая новость заключается в том, что это опубликовал структуру данных, так что я бы начал с Википедии, чтобы разобраться с этим, а затем в Google трудно понять, смогу ли я найти «приличную» реализацию javascript ... или не смог бы просто перенести реализацию Java.

Это небольшая сложная проблема. Мне будет интересно посмотреть, что вы придумали, и что другие люди предлагают по пути. Держите меня в курсе Вилли?

И еще один совет: чаще всего для игры лучше НЕ принимать оптимальных решений; потому что ваш противник, «простой человек», совершенно не способен рассчитать хорошую (не говоря уже об оптимальной) комбинацию «6 из 25 сил» за секунду, и вероятность того, что они получат лучшую комбинацию случайно, составляет 1 в 25 * 24 * 23 * 22 * ​​21 * 20 = 127 512 000 ... особенно, если эти "способности" используют друг друга "секретными" способами ... даже если секреты будут опубликованы, "математикам понадобится", чтобы заняться математикой достаточно для достижения результата «выше среднего». Вы понимаете, о чем я?

Приветствия. Кит.

Answer 3

1. Да, это 25C6 (что на самом деле ~ 177k)

2. , например, дубликат. Перечислите все возможные комбинации k целых чисел от 1 ... n (n выберите k) и Как перебирать каждую возможную комбинацию из n игральных карт .
   Если вы знаететам будет всего 6 предметов, вы можете просто иметь 6 вложенных циклов for (хотя это, очевидно, плохо масштабируется).

3. Конечно, это возможно - 177k комбинацийна крошечную долю секунды, чтобы перебрать на типичном ПК (возможно, немного дольше, так как вы используете Javascript, но не более секунды или двух)