Учитывая набор стеков разной высоты, как выбрать любую возможную комбинацию?

Question

Ввод: общая стоимость.

Вывод: все комбинации уровней, которые дают желаемую стоимость.

Каждый уровень каждого стека стоит разную сумму (уровень 1 в стеке 1 не стоит столько же, сколько уровень 1 в стеке 2). У меня есть функция, которая преобразует уровень в фактическую стоимость на основе базовой стоимости (уровень 1), которую я ввел вручную (жестко запрограммировано).

Мне нужно найти комбинацию уровней, которые дают мне предполагаемую стоимость. Я понимаю, что существует более одного возможного решения, но мне нужен только способ перебора всех возможных вариантов.

Вот что мне нужно:

input = 224, это one решений:

---

Я делаю простую программу, которая должна выбирать уровни различных стеков, а затем вычислять стоимость, и мне нужно знать все возможные возможные затраты ... Каждый уровень каждого стека стоит различную сумму денег, но проблема не в этом, проблема в том, как выбрать один уровень для каждого стека.

Я, вероятно, объяснил это очень расплывчато, так что вот картинка (вам придется извинить мои плохие навыки рисования):

Итак, все стеки имеют уровень 0, а уровень 0 всегда стоит 0 денег.

Дополнительная информация:

• У меня есть массив с именем «maxLevels», длина этого массива - это количество стеков, а каждый элемент - номер самого высокого уровня в этом стеке (например, maxLevels [0] == 2).
• Вы можете выполнять итерации с 1-го уровня, поскольку уровень 0 вообще не имеет значения.
• Выбранные уровни должны быть сохранены в массиве (имя: «currentLevels), который похож на maxLevels (той же длины), но вместо того, чтобы содержать максимальный уровень стека, он содержит выбранный уровень стека (например, : currentLevels [3] == 2).
• Я программирую на C ++, но с псевдокодом тоже все в порядке.
• Это не домашнее задание, я делаю это для развлечения (в основном для игры).

Answer 1

Я не уверен, что понимаю вопрос, но вот как перелистать все возможные комбинации выбора одного предмета из каждого стека (в данном случае 3 * 1 * 2 * 3 * 1 = 18 возможностей):

void visit_each_combination(size_t *maxLevels, size_t num_of_stacks, Visitor &visitor, std::vector<size_t> &choices_so_far) {
    if (num_of_stacks == 0) {
        visitor.visit(choices_so_far);
    } else {
        for (size_t pos = 0; pos <= maxLevels[0]; ++pos) {
            choices_so_far.push_back(pos);
            visit_each_combination(maxLevels+1, num_of_stacks-1, visitor, choices_so_far);
            choices_so_far.pop_back();
        }
    }
}

Вы можете заменить visitor.visit тем, что вы хотите сделать с каждой комбинацией, чтобы сделать код более конкретным. Я использовал вектор choices_so_far вместо вашего массива currentLevels, но он мог бы также работать с массивом.

Answer 2

Я решил это, я думаю. @ Стив Джессоп дал мне идею использовать рекурсию.

Алгоритм:

circ(currentStack)
{
    for (i = 0; i <= allStacks[currentStack]; i ++)           
       if (currentStack == lastStack && i == allStacks[currentStack])
           return 0;
       else if (currentStack != lastStack)
           circ(++ currentStack);
}

Answer 3

Это очень просто, если я правильно понял. Минимальная стоимость равна 0, а максимальная стоимость равна сумме высот стеков. Чтобы достичь какой-либо конкретной стоимости между этими пределами, вы можете начать слева, выбирая максимальный уровень для каждого стека до тех пор, пока ваша цель не будет достигнута, а затем выберите уровень 0 для оставшихся стеков. (Возможно, вам придется настроить последний ненулевой стек, если вы не достигли цели.)