枚举可能的配置
Enumerate possible configurations
在电脑游戏中，您可以建造四种类型的单位。每个单元都有一定的相关成本。此外，您对可以花费的资源数量有限制。
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 problem。这是子集求和问题的特殊变体还是其他名称？
你可以使用背包来解决这个问题，有一些变体可以打印出所有可能的解决方案。
如果你想实现更简单的东西，但在更大的实例上效率不高，你可以使用简单的递归函数：
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)
...
一个可能的解决方案是使用 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]]
您的问题与integer partitioning数学密切相关。
想象一下找零钱。例如，如果您找零 0.87 美元，您可以使用 3 个硬币，每个 25 美分，加上 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 美分硬币视为 "leftovers" 或 "wastage." 我知道您实际上并没有 1 美分硬币，但是如果你假设玩家购买了一件 null/wastage 物品。
在电脑游戏中，您可以建造四种类型的单位。每个单元都有一定的相关成本。此外，您对可以花费的资源数量有限制。
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 problem。这是子集求和问题的特殊变体还是其他名称？
你可以使用背包来解决这个问题，有一些变体可以打印出所有可能的解决方案。
如果你想实现更简单的东西，但在更大的实例上效率不高，你可以使用简单的递归函数：
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)
...
一个可能的解决方案是使用 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]]
您的问题与integer partitioning数学密切相关。
想象一下找零钱。例如，如果您找零 0.87 美元，您可以使用 3 个硬币，每个 25 美分，加上 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 美分硬币视为 "leftovers" 或 "wastage." 我知道您实际上并没有 1 美分硬币，但是如果你假设玩家购买了一件 null/wastage 物品。