Recently, I was playing one of my favorites games, and I came accross a problem: This game have a store, and in that store, skins to especific characters are selled, and I'm planning to buy them. There is 34 skins avaliable, and each one costs 1800 credits (the game currency). The only way of earning those credits is buying packs of it with real money.
There is 6 packs, as I show below:
| 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 |
My first tought was to calculate what was the best way (aka the way of spending less money) to buy any quantity of skins (1 -> 34), but buying N amount of just a single type of pack. So, I wrote this code:
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
That gave me the following output:
| 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 |
Now, my question is: Is there a way to calculate and get the best combination of packs mixed or not, for each number of skins?
I didn't think of anything but to first calculate the maximum amount of packs which I would need to buy all the 34 skins (102 packs of 600 credits). But I got stuck on this tought, and hope for you to help me solve this!
Thank you all, in advance!
What you are trying to solve here is a variation of the Knapsack Problem. This means there is no solution in polynomial time possible.
However you can do a few optimizations: In No circumstance will somebody buy pack #2. It is strictly inferior to buying 2 (or 1) pack #1, therefore we can immediately eliminate it for the algorithm so it does not have to waste time on it ;)
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: https://stackoverflow.com/a/7748851/12998205
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)}