Перечислите возможные конфигурации

Question

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

limit = 18
costs = [2, 5, 7, 10]

Используя Python, я хочу перечислить все возможные конфигурации модулей, которые вы можете построить. Для приведенного выше примера допустимы следующие конфигурации:

2 2 2 2 2 2 2 2 2 (=18)
5 5 5 2 (=17)
10 2 2 2 2 (=18)
10 7 (=17)
...

Вопрос. Как называется эта проблема в информатике? Я знаю, что существует проблема Subset sum . Это особый вариант задачи о сумме подмножеств или он называется как-то еще?

Answer 1

Возможным решением является использование itertools. Хитрость в том, чтобы рассчитать максимальное количество пар, которые вы можете создать. Вы делаете это путем деления лимита на минимальную стоимость.

import itertools

limit = 18
costs = [2, 5, 7, 10]

res=[]
nmax=int(limit/min(costs))
for i in range(1,nmax):
    a=itertools.combinations_with_replacement(costs, i)
    a = [list(row) for row in a]
    for j in a:
        if(sum(j)<=limit):
            res.append(j)
print(res)

[[2], [5], [7], [10], [2, 2], [2, 5],[2, 7], [2, 10], [5, 5], [5, 7], [5, 10], [7, 7], [7, 10], [2, 2, 2],[2, 2, 5], [2, 2, 7], [2, 2, 10], [2, 5, 5], [2, 5, 7], [2, 5, 10], [2, 7, 7], [5, 5, 5], [5, 5, 7], [2, 2, 2, 2], [2, 2, 2, 5], [2, 2, 2, 7], [2, 2, 2, 10], [2, 2, 5, 5], [2, 2, 5, 7], [2, 2, 7, 7], [2, 5, 5, 5], [2, 2, 2, 2, 2], [2, 2, 2, 2, 5], [2, 2, 2, 2, 7], [2, 2, 2, 2, 10],[2, 2, 2, 5, 5], [2, 2, 2, 5, 7], [2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 2, 7], [2, 2, 2, 2, 5, 5], [2, 2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 2, 2, 2, 2]]

Answer 2

Ваша проблема тесно связана с целочисленным разбиением в математике.

Представьте, что вы меняете сумму в долларах. Например, если вы вносите изменения за 0,87 долл. США, вы можете использовать 3 монеты по 25 plus каждая, плюс 1 монету по 10 ¢, плюс 2 монеты по 1 *.

import functools
import sys
import copy

class PossibilityMaker:
    log_progress = lambda *args, sep=" ", end="\n", print=print, file=sys.stderr:\
        print(*args, sep=sep, end=end, file=file)

    log_progress = lambda *args, **kwargs: None

    @classmethod
    def get_possibilities(cls, total:int, denominations):
        assert(isinstance(total, int))
        denominations = set(denominations)
        possibilities = list()
        cls.get_possibilities_helper(total, denominations, possibilities, dict())
        return possibilities

    @classmethod
    def get_possibilities_helper(cls, total:int, denominations:set, possibilities:list, partial):
        assert(isinstance(total, int))
        cls.log_progress("making change for", total, "cent(s) using coins", denominations)
        if len(denominations) < 1:
            partial = copy.copy(partial)
            partial[1] = total
            possibilities.append(partial)
            cls.log_progress(partial)
            del partial
        else:
            max_denom = max(denominations)
            cls.log_progress("largest coin is", max_denom, "cent(s)")
            max_coin_quantity = total//max_denom
            for coin_quantity in range(max_coin_quantity + 1):
                cls.log_progress("Using", coin_quantity, "of coin of size", max_denom)
                next_partial = copy.deepcopy(partial)
                next_partial[max_denom] = coin_quantity
                next_total = total - coin_quantity * max_denom
                next_denominations = copy.deepcopy(denominations)
                next_denominations.remove(max_denom)
                cls.get_possibilities_helper(next_total, next_denominations, possibilities, next_partial)
            return

possibilities = PossibilityMaker.get_possibilities(18, [2, 5, 7, 10])

print(60*"#")

print(
    "\n".join(
        str(possibility) for possibility in possibilities
    )
)

Вывод:

{10: 0, 7: 0, 5: 0, 2: 0, 1: 18}
{10: 0, 7: 0, 5: 0, 2: 1, 1: 16}
{10: 0, 7: 0, 5: 0, 2: 2, 1: 14}
{10: 0, 7: 0, 5: 0, 2: 3, 1: 12}
{10: 0, 7: 0, 5: 0, 2: 4, 1: 10}
{10: 0, 7: 0, 5: 0, 2: 5, 1: 8}
{10: 0, 7: 0, 5: 0, 2: 6, 1: 6}
{10: 0, 7: 0, 5: 0, 2: 7, 1: 4}
{10: 0, 7: 0, 5: 0, 2: 8, 1: 2}
{10: 0, 7: 0, 5: 0, 2: 9, 1: 0}
{10: 0, 7: 0, 5: 1, 2: 0, 1: 13}
{10: 0, 7: 0, 5: 1, 2: 1, 1: 11}
{10: 0, 7: 0, 5: 1, 2: 2, 1: 9}
{10: 0, 7: 0, 5: 1, 2: 3, 1: 7}
{10: 0, 7: 0, 5: 1, 2: 4, 1: 5}
{10: 0, 7: 0, 5: 1, 2: 5, 1: 3}
{10: 0, 7: 0, 5: 1, 2: 6, 1: 1}
{10: 0, 7: 0, 5: 2, 2: 0, 1: 8}
{10: 0, 7: 0, 5: 2, 2: 1, 1: 6}
{10: 0, 7: 0, 5: 2, 2: 2, 1: 4}
{10: 0, 7: 0, 5: 2, 2: 3, 1: 2}
{10: 0, 7: 0, 5: 2, 2: 4, 1: 0}
{10: 0, 7: 0, 5: 3, 2: 0, 1: 3}
{10: 0, 7: 0, 5: 3, 2: 1, 1: 1}
{10: 0, 7: 1, 5: 0, 2: 0, 1: 11}
{10: 0, 7: 1, 5: 0, 2: 1, 1: 9}
{10: 0, 7: 1, 5: 0, 2: 2, 1: 7}
{10: 0, 7: 1, 5: 0, 2: 3, 1: 5}
{10: 0, 7: 1, 5: 0, 2: 4, 1: 3}
{10: 0, 7: 1, 5: 0, 2: 5, 1: 1}
{10: 0, 7: 1, 5: 1, 2: 0, 1: 6}
{10: 0, 7: 1, 5: 1, 2: 1, 1: 4}
{10: 0, 7: 1, 5: 1, 2: 2, 1: 2}
{10: 0, 7: 1, 5: 1, 2: 3, 1: 0}
{10: 0, 7: 1, 5: 2, 2: 0, 1: 1}
{10: 0, 7: 2, 5: 0, 2: 0, 1: 4}
{10: 0, 7: 2, 5: 0, 2: 1, 1: 2}
{10: 0, 7: 2, 5: 0, 2: 2, 1: 0}
{10: 1, 7: 0, 5: 0, 2: 0, 1: 8}
{10: 1, 7: 0, 5: 0, 2: 1, 1: 6}
{10: 1, 7: 0, 5: 0, 2: 2, 1: 4}
{10: 1, 7: 0, 5: 0, 2: 3, 1: 2}
{10: 1, 7: 0, 5: 0, 2: 4, 1: 0}
{10: 1, 7: 0, 5: 1, 2: 0, 1: 3}
{10: 1, 7: 0, 5: 1, 2: 1, 1: 1}
{10: 1, 7: 1, 5: 0, 2: 0, 1: 1}

Вы можете рассматривать монеты в 1 цент как «остатки» или «потери». Я понимаю, что у вас на самом деле нет монет в 1 цент, но все всегда складывается с вашим limit = 18, если вы представляете, что игрок купил предмет с нулевым расходом / потерей.

Answer 3

Вы можете решить это, используя рюкзак, есть варианты, которые распечатывают все возможные решения.

Если вы хотите реализовать что-то более простое, но не столь эффективное в больших случаях, вы можете использовать простую рекурсивную функцию:

def f(costs, limit, sofar, _sum ):
    if not costs or limit < 0:
        if limit >= 0:
            print(f"{sofar}(={_sum})")
    else:
        f(costs, limit -costs[0], sofar + str(costs[0])+ " ", _sum + costs[0])
        f(costs[1:], limit, sofar, _sum)


f([2,5,7,10], 18, "", 0)

Это даст:

...
2 5 5 5 (=17)
2 5 5 (=12)
2 5 7 (=14)
2 5 10 (=17)
2 5 (=7)
2 7 7 (=16)
2 7 (=9)
2 10 (=12)
2 (=2)
...