如何改进我的优化算法？
How to improve my Optimization algorithm?
最近在玩我最喜欢的一款游戏时，遇到了一个问题：
这个游戏有一个商店，在那个商店里，出售特定角色的皮肤，我打算购买它们。
共有 34 款皮肤，每款售价 1800 积分（游戏币）。
获得这些积分的唯一方法是用真钱购买一包。
有6包，如下图：
Pack
Amount of credits
Price
1
600
19.90
2
1200
41.50
3
2670
83.50
4
4920
144.90
5
7560
207.90
6
16000
414.90
我的第一个问题是计算购买任意数量的皮肤 (1 -> 34) 的最佳方式（也就是花更少的钱的方式），但只购买 N 种类型的皮肤。
所以，我写了这段代码：
import numpy as np
import pandas as pd
#Cost per Skin (Cs)
c_ps = 1800
#Amount of credits per pack (Qp)
q_ppc = [600, 1200, 2670, 4920, 7560, 16000]
#Cost per pack (Cp)
c_ppc = [19.9, 41.5, 83.3, 144.9, 207.9, 414.9]
#Amount of skins to be buyed (Qd)
qtd_d = 0
#Total cost of the transaction (Ct)
ct_total = 0
#Total amount of packs (Pt)
qtd_total = 0
#Complete list
lista_completa = np.zeros((34,4), dtype=np.float16)
#count var
j = 0
while True:
#best option (Bb)
best_opt = 0
#best amount (Bq)
best_qtd = 0
#best cost (Bc)
best_cost = 50000
qtd_d += 1
#Cost of the nº of skins to be buyed
custo = (c_ps * qtd_d)
for opt in q_ppc:
i = q_ppc.index(opt)
qtd_total = m.ceil(custo/opt)
ct_total = (qtd_total * c_ppc[i])
if best_cost > ct_total:
best_opt = opt
best_qtd = qtd_total
best_cost = ct_total
lista_completa[j] = [int(qtd_d), int(best_opt), int(best_qtd), float(np.round(best_cost, decimals = 1))]
j += 1
if j == 34:
break
float_formatter = '{:.2F}'.format
np.set_printoptions(formatter={'float_kind':float_formatter})
pd.set_option('display.float_format','{:.2f}'.format)
df = pd.DataFrame(lista_completa, columns = ['Quantidade desejada',
'Melhor opção de pacote',
'Quantidade de pacotes necessária',
'Custo total'])
df.set_index('Quantidade desejada', inplace = True)
df
这给了我以下输出：
Amount of Skins
Best pack option
Required amount of packs
Final Cost
1.00
600.00
3.00
59.69
2.00
600.00
6.00
119.38
3.00
600.00
9.00
179.12
4.00
7560.00
1.00
207.88
5.00
4920.00
2.00
289.75
6.00
600.00
18.00
358.25
7.00
16000.00
1.00
415.00
8.00
16000.00
1.00
415.00
9.00
600.00
27.00
537.50
10.00
4920.00
4.00
579.50
11.00
7560.00
3.00
623.50
12.00
7560.00
3.00
623.50
13.00
4920.00
5.00
724.50
14.00
16000.00
2.00
830.00
15.00
16000.00
2.00
830.00
16.00
16000.00
2.00
830.00
17.00
16000.00
2.00
830.00
18.00
4920.00
7.00
1014.50
19.00
4920.00
7.00
1014.50
20.00
7560.00
5.00
1040.00
21.00
7560.00
5.00
1040.00
22.00
16000.00
3.00
1245.00
23.00
16000.00
3.00
1245.00
24.00
16000.00
3.00
1245.00
25.00
16000.00
3.00
1245.00
26.00
16000.00
3.00
1245.00
27.00
4920.00
10.00
1449.00
28.00
7560.00
7.00
1455.00
29.00
7560.00
7.00
1455.00
30.00
4920.00
11.00
1594.00
31.00
16000.00
4.00
1660.00
32.00
16000.00
4.00
1660.00
33.00
16000.00
4.00
1660.00
34.00
16000.00
4.00
1660.00
现在，我的问题是：
有没有一种方法可以针对每个皮肤数量计算并获得最佳组合 mixed？
除了首先计算我需要购买所有 34 种皮肤（102 包 600 积分）的最大包数，我什么也没想到。但是一直卡在这个问题上，希望大家帮我解决！
提前谢谢大家！
您在这里要解决的是 Knapsack Problem 的变体。这意味着在多项式时间内没有可能的解决方案。
不过你可以做一些优化：
在没有的情况下会有人购买包#2。它绝对不如购买 2（或 1）包 #1，因此我们可以立即为算法消除它，这样就不必在上面浪费时间；）
import math
from pprint import pprint
import numpy as np
def cheapest_option(
pack_credits: np.ndarray,
pack_costs: np.ndarray,
# generalize problem to arbitrary amounts of credits
# not just multiples of 1_800
min_credits: int,
prev_assignment: np.ndarray = None):
def permut(total: int, length: int, at_least: int):
"""
adapted from:
Creates all possible permutations of length `length` such that
`at_least <= sum(permutation) <= total`
"""
if length == 1:
if at_least >= 0:
yield [at_least]
else:
yield [total]
else:
for i in range(total + 1):
n_tot = total - i
if n_tot == 0:
yield [i] + [0] * (length - 1)
else:
for permutation in permut(n_tot, length - 1, at_least - i):
yield [i] + permutation
# if previous assignment would be enough to cover the required amount of credits
# we can just re-use that optimal solution, since we know it is optimal
if prev_assignment is not None:
prev_credits = prev_assignment.dot(pack_credits)
if prev_credits >= min_credits:
return prev_assignment.copy(), round(prev_assignment.dot(pack_costs), 2)
# the mackimum amount of packs is reached when we ONLY buy the cheapest one
# this serves as an upper bound for the number of packs we have to buy
n_packs_most = math.ceil(min_credits / pack_credits[0])
# analogously the least amounts of packs we have to buy
# is if we only buy the most expensive one
n_packs_least = math.ceil(min_credits / pack_credits[-1])
# create permutation table as numpy array for fast lookups
# convert to float so np.dot does not have to convert the array each time
table = np.asarray(
list(permut(n_packs_most, len(pack_credits), n_packs_least)),
dtype=float
)
# our initial guess
optimal = np.zeros_like(pack_credits)
optimal[0] = n_packs_most
optimal_costs = optimal.dot(pack_costs)
for assignment in table:
# skip assignments that do not reach the required credits
if assignment.dot(pack_credits) >= min_credits:
curr_costs = assignment.dot(pack_costs)
# update with new best solution
if curr_costs < optimal_costs:
optimal, optimal_costs = assignment, curr_costs
# convert back to int
return optimal.astype(int), round(optimal.dot(pack_costs))
# store as floats to speed up np.dot-calls
pack_credits = np.asarray([600., 2_670., 4_920., 7_560., 16_000.])
pack_costs = np.asarray([19.90, 83.30, 144.90, 207.90, 414.90])
skin_cost = 1_800
opt_ass, opt_cost = cheapest_option(pack_credits, pack_costs, min_credits=skin_cost)
results_optimal = {1: (opt_ass, opt_cost)}
# still takes around a minute to complete
for n_skins in range(2, 35):
results_optimal[n_skins] = (opt_ass, opt_cost) = \
cheapest_option(
pack_credits,
pack_costs,
min_credits=n_skins * skin_cost,
# attempt to reuse previous solution
prev_assignment=opt_ass
)
pprint(results_optimal)
{1: (array([3, 0, 0, 0, 0]), 59.7),
2: (array([6, 0, 0, 0, 0]), 119.4),
3: (array([9, 0, 0, 0, 0]), 179.1),
4: (array([0, 0, 0, 1, 0]), 207.9),
5: (array([15, 0, 0, 0, 0]), 298.5),
6: (array([18, 0, 0, 0, 0]), 358.2),
7: (array([0, 0, 0, 0, 1]), 414.9),
8: (array([0, 0, 0, 0, 1]), 414.9),
9: (array([1, 0, 0, 0, 1]), 434.8),
10: (array([0, 1, 0, 0, 1]), 498.2),
11: (array([0, 0, 1, 0, 1]), 559.8),
12: (array([0, 0, 0, 1, 1]), 622.8),
13: (array([0, 0, 0, 1, 1]), 622.8),
14: (array([0, 0, 0, 0, 2]), 829.8),
15: (array([0, 0, 0, 0, 2]), 829.8),
16: (array([0, 0, 0, 0, 2]), 829.8),
17: (array([0, 0, 0, 0, 2]), 829.8),
18: (array([1, 0, 0, 0, 2]), 849.7),
19: (array([0, 1, 0, 0, 2]), 913.1),
20: (array([0, 0, 1, 0, 2]), 974.7),
21: (array([0, 0, 0, 1, 2]), 1037.7),
22: (array([0, 0, 0, 0, 3]), 1244.7),
23: (array([0, 0, 0, 0, 3]), 1244.7),
24: (array([0, 0, 0, 0, 3]), 1244.7),
25: (array([0, 0, 0, 0, 3]), 1244.7),
26: (array([0, 0, 0, 0, 3]), 1244.7),
27: (array([1, 0, 0, 0, 3]), 1264.6),
28: (array([0, 1, 0, 0, 3]), 1328.0),
29: (array([0, 0, 1, 0, 3]), 1389.6),
30: (array([0, 0, 0, 1, 3]), 1452.6),
31: (array([0, 0, 0, 0, 4]), 1659.6),
32: (array([0, 0, 0, 0, 4]), 1659.6),
33: (array([0, 0, 0, 0, 4]), 1659.6),
34: (array([0, 0, 0, 0, 4]), 1659.6)}
最近在玩我最喜欢的一款游戏时，遇到了一个问题： 这个游戏有一个商店，在那个商店里，出售特定角色的皮肤，我打算购买它们。 共有 34 款皮肤，每款售价 1800 积分（游戏币）。 获得这些积分的唯一方法是用真钱购买一包。
有6包，如下图：
| Pack | Amount of credits | Price |
|---|---|---|
| 1 | 600 | 19.90 |
| 2 | 1200 | 41.50 |
| 3 | 2670 | 83.50 |
| 4 | 4920 | 144.90 |
| 5 | 7560 | 207.90 |
| 6 | 16000 | 414.90 |
我的第一个问题是计算购买任意数量的皮肤 (1 -> 34) 的最佳方式（也就是花更少的钱的方式），但只购买 N 种类型的皮肤。 所以，我写了这段代码：
import numpy as np
import pandas as pd
#Cost per Skin (Cs)
c_ps = 1800
#Amount of credits per pack (Qp)
q_ppc = [600, 1200, 2670, 4920, 7560, 16000]
#Cost per pack (Cp)
c_ppc = [19.9, 41.5, 83.3, 144.9, 207.9, 414.9]
#Amount of skins to be buyed (Qd)
qtd_d = 0
#Total cost of the transaction (Ct)
ct_total = 0
#Total amount of packs (Pt)
qtd_total = 0
#Complete list
lista_completa = np.zeros((34,4), dtype=np.float16)
#count var
j = 0
while True:
#best option (Bb)
best_opt = 0
#best amount (Bq)
best_qtd = 0
#best cost (Bc)
best_cost = 50000
qtd_d += 1
#Cost of the nº of skins to be buyed
custo = (c_ps * qtd_d)
for opt in q_ppc:
i = q_ppc.index(opt)
qtd_total = m.ceil(custo/opt)
ct_total = (qtd_total * c_ppc[i])
if best_cost > ct_total:
best_opt = opt
best_qtd = qtd_total
best_cost = ct_total
lista_completa[j] = [int(qtd_d), int(best_opt), int(best_qtd), float(np.round(best_cost, decimals = 1))]
j += 1
if j == 34:
break
float_formatter = '{:.2F}'.format
np.set_printoptions(formatter={'float_kind':float_formatter})
pd.set_option('display.float_format','{:.2f}'.format)
df = pd.DataFrame(lista_completa, columns = ['Quantidade desejada',
'Melhor opção de pacote',
'Quantidade de pacotes necessária',
'Custo total'])
df.set_index('Quantidade desejada', inplace = True)
df
这给了我以下输出：
| Amount of Skins | Best pack option | Required amount of packs | Final Cost |
|---|---|---|---|
| 1.00 | 600.00 | 3.00 | 59.69 |
| 2.00 | 600.00 | 6.00 | 119.38 |
| 3.00 | 600.00 | 9.00 | 179.12 |
| 4.00 | 7560.00 | 1.00 | 207.88 |
| 5.00 | 4920.00 | 2.00 | 289.75 |
| 6.00 | 600.00 | 18.00 | 358.25 |
| 7.00 | 16000.00 | 1.00 | 415.00 |
| 8.00 | 16000.00 | 1.00 | 415.00 |
| 9.00 | 600.00 | 27.00 | 537.50 |
| 10.00 | 4920.00 | 4.00 | 579.50 |
| 11.00 | 7560.00 | 3.00 | 623.50 |
| 12.00 | 7560.00 | 3.00 | 623.50 |
| 13.00 | 4920.00 | 5.00 | 724.50 |
| 14.00 | 16000.00 | 2.00 | 830.00 |
| 15.00 | 16000.00 | 2.00 | 830.00 |
| 16.00 | 16000.00 | 2.00 | 830.00 |
| 17.00 | 16000.00 | 2.00 | 830.00 |
| 18.00 | 4920.00 | 7.00 | 1014.50 |
| 19.00 | 4920.00 | 7.00 | 1014.50 |
| 20.00 | 7560.00 | 5.00 | 1040.00 |
| 21.00 | 7560.00 | 5.00 | 1040.00 |
| 22.00 | 16000.00 | 3.00 | 1245.00 |
| 23.00 | 16000.00 | 3.00 | 1245.00 |
| 24.00 | 16000.00 | 3.00 | 1245.00 |
| 25.00 | 16000.00 | 3.00 | 1245.00 |
| 26.00 | 16000.00 | 3.00 | 1245.00 |
| 27.00 | 4920.00 | 10.00 | 1449.00 |
| 28.00 | 7560.00 | 7.00 | 1455.00 |
| 29.00 | 7560.00 | 7.00 | 1455.00 |
| 30.00 | 4920.00 | 11.00 | 1594.00 |
| 31.00 | 16000.00 | 4.00 | 1660.00 |
| 32.00 | 16000.00 | 4.00 | 1660.00 |
| 33.00 | 16000.00 | 4.00 | 1660.00 |
| 34.00 | 16000.00 | 4.00 | 1660.00 |
现在，我的问题是： 有没有一种方法可以针对每个皮肤数量计算并获得最佳组合 mixed？
除了首先计算我需要购买所有 34 种皮肤（102 包 600 积分）的最大包数，我什么也没想到。但是一直卡在这个问题上，希望大家帮我解决！
提前谢谢大家！
您在这里要解决的是 Knapsack Problem 的变体。这意味着在多项式时间内没有可能的解决方案。
不过你可以做一些优化： 在没有的情况下会有人购买包#2。它绝对不如购买 2（或 1）包 #1，因此我们可以立即为算法消除它，这样就不必在上面浪费时间；）
import math
from pprint import pprint
import numpy as np
def cheapest_option(
pack_credits: np.ndarray,
pack_costs: np.ndarray,
# generalize problem to arbitrary amounts of credits
# not just multiples of 1_800
min_credits: int,
prev_assignment: np.ndarray = None):
def permut(total: int, length: int, at_least: int):
"""
adapted from:
Creates all possible permutations of length `length` such that
`at_least <= sum(permutation) <= total`
"""
if length == 1:
if at_least >= 0:
yield [at_least]
else:
yield [total]
else:
for i in range(total + 1):
n_tot = total - i
if n_tot == 0:
yield [i] + [0] * (length - 1)
else:
for permutation in permut(n_tot, length - 1, at_least - i):
yield [i] + permutation
# if previous assignment would be enough to cover the required amount of credits
# we can just re-use that optimal solution, since we know it is optimal
if prev_assignment is not None:
prev_credits = prev_assignment.dot(pack_credits)
if prev_credits >= min_credits:
return prev_assignment.copy(), round(prev_assignment.dot(pack_costs), 2)
# the mackimum amount of packs is reached when we ONLY buy the cheapest one
# this serves as an upper bound for the number of packs we have to buy
n_packs_most = math.ceil(min_credits / pack_credits[0])
# analogously the least amounts of packs we have to buy
# is if we only buy the most expensive one
n_packs_least = math.ceil(min_credits / pack_credits[-1])
# create permutation table as numpy array for fast lookups
# convert to float so np.dot does not have to convert the array each time
table = np.asarray(
list(permut(n_packs_most, len(pack_credits), n_packs_least)),
dtype=float
)
# our initial guess
optimal = np.zeros_like(pack_credits)
optimal[0] = n_packs_most
optimal_costs = optimal.dot(pack_costs)
for assignment in table:
# skip assignments that do not reach the required credits
if assignment.dot(pack_credits) >= min_credits:
curr_costs = assignment.dot(pack_costs)
# update with new best solution
if curr_costs < optimal_costs:
optimal, optimal_costs = assignment, curr_costs
# convert back to int
return optimal.astype(int), round(optimal.dot(pack_costs))
# store as floats to speed up np.dot-calls
pack_credits = np.asarray([600., 2_670., 4_920., 7_560., 16_000.])
pack_costs = np.asarray([19.90, 83.30, 144.90, 207.90, 414.90])
skin_cost = 1_800
opt_ass, opt_cost = cheapest_option(pack_credits, pack_costs, min_credits=skin_cost)
results_optimal = {1: (opt_ass, opt_cost)}
# still takes around a minute to complete
for n_skins in range(2, 35):
results_optimal[n_skins] = (opt_ass, opt_cost) = \
cheapest_option(
pack_credits,
pack_costs,
min_credits=n_skins * skin_cost,
# attempt to reuse previous solution
prev_assignment=opt_ass
)
pprint(results_optimal)
{1: (array([3, 0, 0, 0, 0]), 59.7),
2: (array([6, 0, 0, 0, 0]), 119.4),
3: (array([9, 0, 0, 0, 0]), 179.1),
4: (array([0, 0, 0, 1, 0]), 207.9),
5: (array([15, 0, 0, 0, 0]), 298.5),
6: (array([18, 0, 0, 0, 0]), 358.2),
7: (array([0, 0, 0, 0, 1]), 414.9),
8: (array([0, 0, 0, 0, 1]), 414.9),
9: (array([1, 0, 0, 0, 1]), 434.8),
10: (array([0, 1, 0, 0, 1]), 498.2),
11: (array([0, 0, 1, 0, 1]), 559.8),
12: (array([0, 0, 0, 1, 1]), 622.8),
13: (array([0, 0, 0, 1, 1]), 622.8),
14: (array([0, 0, 0, 0, 2]), 829.8),
15: (array([0, 0, 0, 0, 2]), 829.8),
16: (array([0, 0, 0, 0, 2]), 829.8),
17: (array([0, 0, 0, 0, 2]), 829.8),
18: (array([1, 0, 0, 0, 2]), 849.7),
19: (array([0, 1, 0, 0, 2]), 913.1),
20: (array([0, 0, 1, 0, 2]), 974.7),
21: (array([0, 0, 0, 1, 2]), 1037.7),
22: (array([0, 0, 0, 0, 3]), 1244.7),
23: (array([0, 0, 0, 0, 3]), 1244.7),
24: (array([0, 0, 0, 0, 3]), 1244.7),
25: (array([0, 0, 0, 0, 3]), 1244.7),
26: (array([0, 0, 0, 0, 3]), 1244.7),
27: (array([1, 0, 0, 0, 3]), 1264.6),
28: (array([0, 1, 0, 0, 3]), 1328.0),
29: (array([0, 0, 1, 0, 3]), 1389.6),
30: (array([0, 0, 0, 1, 3]), 1452.6),
31: (array([0, 0, 0, 0, 4]), 1659.6),
32: (array([0, 0, 0, 0, 4]), 1659.6),
33: (array([0, 0, 0, 0, 4]), 1659.6),
34: (array([0, 0, 0, 0, 4]), 1659.6)}