I have a Python coding task that appears to be some kind of variation of either bin-packing or knapsack problem, I'm not entirely sure. I have an option that seems to work, but I don't think it's the correct solution per se, as there may be edge cases that could fail. (I'm not a CS or math student, so my knowledge in algorithms/combinatorics is quite rudimentary.)
The problem
A user can choose a configuration of 3 data types:
- Small data is 1 GB
- Medium data is 1.5 GB
- Large data is 2 GB
The console app asks: "How many small pieces you need? Medium? Large?", in order. I need to fit these pieces of data into the cheapest server configuration:
- Small server holds 10 GB, costs $68.84
- Medium server holds 24 GB, costs $140.60
- Large server holds 54 GB, costs $316.09
So for example, if the user chooses a total of 20 GB of data, the function should note that it would be cheaper to use 2 small servers rather than 1 medium server.
The function that I wrote primarily uses division to look for whole numbers, with floor/ceil calls wherever appropriate. I wrote blocks that sequentially go through a configuration with just L servers, then L & M, then L, M & S, etc.
Here is the function:
def allocate_servers(setup):
'''This function allocates servers based on user's inputs.'''
# setup is a dict of type {'S':int, 'M':int, 'L':int}, each is amount of data needed
# Global variables that initialise to 0
global COUNTER_S
global COUNTER_M
global COUNTER_L
# Calculate total size need
total_size = setup['S'] * PLANET_SIZES['S'] + \
setup['M'] * PLANET_SIZES['M'] + \
setup['L'] * PLANET_SIZES['L']
print('\nTotal size requirement: {} GB\n'.format(total_size))
# Find cheapest server combo
# 1. Using just large servers
x = total_size / SERVERS['L']['cap'] # Here and later cap is server capacity, eg 54 in this case
if x <= 1:
COUNTER_L = 1
else:
COUNTER_L = int(ceil(x))
option = generate_option(COUNTER_S, COUNTER_M, COUNTER_L) # this function creates a dict and calculates prices
OPTIONS.append(option)
reset_counters()
# 2. Using large and medium servers
if x <= 1:
COUNTER_L = 1
else:
COUNTER_L = int(floor(x))
total_size_temp = total_size - SERVERS['L']['cap'] * COUNTER_L
y = total_size_temp / SERVERS['M']['cap']
if y <= 1:
COUNTER_M = 1
else:
COUNTER_M = int(ceil(y))
option = generate_option(COUNTER_S, COUNTER_M, COUNTER_L)
OPTIONS.append(option)
reset_counters()
# 3. Using large, medium and small servers
if x <= 1:
COUNTER_L = 1
else:
COUNTER_L = int(floor(x))
total_size_temp = total_size - SERVERS['L']['cap'] * COUNTER_L
y = total_size_temp / SERVERS['M']['cap']
if y <= 1:
COUNTER_M = 1
else:
COUNTER_M = int(floor(y))
total_size_temp = total_size_temp - SERVERS['M']['cap'] * COUNTER_M
z = total_size_temp / SERVERS['S']['cap']
if z <= 1:
COUNTER_S = 1
else:
COUNTER_S = int(ceil(z))
option = generate_option(COUNTER_S, COUNTER_M, COUNTER_L)
OPTIONS.append(option)
reset_counters()
# 4. Using large and small servers
if x <= 1:
COUNTER_L = 1
else:
COUNTER_L = int(floor(x))
total_size_temp = total_size - SERVERS['L']['cap'] * COUNTER_L
z = total_size_temp / SERVERS['S']['cap']
if z <= 1:
COUNTER_S = 1
else:
COUNTER_S = int(ceil(z))
option = generate_option(COUNTER_S, COUNTER_M, COUNTER_L)
OPTIONS.append(option)
reset_counters()
# 5. Using just medium servers
y = total_size / SERVERS['M']['cap']
if y <= 1:
COUNTER_M = 1
else:
COUNTER_M = int(ceil(y))
option = generate_option(COUNTER_S, COUNTER_M, COUNTER_L)
OPTIONS.append(option)
reset_counters()
# 6. Using medium and small servers
if y <= 1:
COUNTER_M = 1
else:
COUNTER_M = int(floor(y))
total_size_temp = total_size - SERVERS['M']['cap'] * COUNTER_M
z = total_size_temp / SERVERS['S']['cap']
if z <= 1:
COUNTER_S = 1
else:
COUNTER_S = int(ceil(z))
option = generate_option(COUNTER_S, COUNTER_M, COUNTER_L)
OPTIONS.append(option)
reset_counters()
# 7. Using just small servers
z = total_size / SERVERS['S']['cap']
if z <= 1:
COUNTER_S = 1
else:
COUNTER_S = int(ceil(z))
option = generate_option(COUNTER_S, COUNTER_M, COUNTER_L)
OPTIONS.append(option)
reset_counters()
# Comparing prices of options
cheapest = min(OPTIONS, key = lambda option: option['total_price'])
return cheapest
I have a sense that something is wrong here. For example, when I input 100 small data, 350 medium and 50 large, I get this output:
Total size requirement: 725.0 GB
All calculated options:
[{'L': 14, 'M': 0, 'S': 0, 'total_price': 4425.259999999999},
{'L': 13, 'M': 1, 'S': 0, 'total_price': 4249.77},
{'L': 13, 'M': 1, 'S': 0, 'total_price': 4249.77},
{'L': 13, 'M': 0, 'S': 3, 'total_price': 4315.6900000000005},
{'L': 0, 'M': 31, 'S': 0, 'total_price': 4358.599999999999},
{'L': 0, 'M': 30, 'S': 1, 'total_price': 4286.84},
{'L': 0, 'M': 0, 'S': 73, 'total_price': 5025.320000000001}]
For the chosen planets you need:
0 Small servers
1 Medium servers
13 Large servers
Price: $4249.77
The function seems to work as intended; however, I just manually checked that, for example, if I was to take 29 medium servers that leaves us with 725-696 = 29 GB, which I could fit onto 3 small servers. Total cost for 29 medium and 3 small is $4283.92, which is cheaper than the M : 30, S : 1 option, but doesn't even make it into the list.
What am I missing here? I have a feeling that my algorithm is very crude and I'm potentially missing out on more optimal solutions.
Do I need to literally go through every possible option, eg for 14/13/12/11/10... large servers, with medium/small combinations also iterating through every option?
EDIT: I had a limited amount of time to solve this problem, so I managed to brute force it. I added for loops in my function, iterating over every possible result. So first with maximum amount of Large servers (say, 14), then 13 Large and rest Medium, then 12 Large and rest Medium, etc... It takes a while to run with large numbers (10k of each data type took maybe like 20 seconds?), but it seems to work.