我有一个Python编码任务，它似乎是垃圾箱或背包问题的某种变体，我不完全确定。我有一个似乎有效的选择，但我不认为这是正确的解决方案，因为可能存在失败的边缘情况。(我不是计算机科学或数学专业的学生，所以我在算法/组合学方面的知识相当初级。)
问题用户可以选择3种数据类型的配置:
小- 数据为1gb
- 数据为1.5 GB
- 数据为2gb
控制台应用程序问:"你需要多少小部件?媒介?大?"，顺序。我需要将这些数据块放入最便宜的服务器配置中:
小- 服务器容量10gb，价格68.84美元
- 服务器容量24gb，价格140.60美元
- 服务器容量54gb，售价316.09美元
因此，例如，如果用户选择总共20gb的数据，该函数应该注意到使用2个小型服务器比使用1个中型服务器更便宜。
我编写的函数主要使用除法来查找整数，并在适当的地方使用floor/ceil调用。我写的块顺序地通过一个配置只有L服务器，然后L &M，然后L, M &年代,等。
函数如下:
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: {} GBn'.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
我有一种不对劲的感觉。例如，当我输入100个小数据，350个中等数据和50个大数据时，我得到这样的输出:
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
函数似乎按预期工作;但是，我只是手动检查，例如，如果我要使用29个中型服务器，那么我们将剩下725-696 = 29 GB，我可以将其放入3个小型服务器上。29个中号和3个小号的总成本是4283.92美元，比M: 30, S: 1的选择便宜，但甚至没有进入列表。
我在这里错过了什么?我有一种感觉，我的算法非常粗糙，我可能会错过更优的解决方案。
我是否需要逐字逐句地检查每一个可能的选项，例如14/13/12/11/10…大型服务器，中型/小型组合也迭代每个选项?
编辑:我解决这个问题的时间有限，所以我设法强行解决它。我在函数中添加了for循环，遍历所有可能的结果。所以首先是最大数量的大型服务器(比如14个)，然后是13个大型服务器，其余的中型服务器，然后是12个大型服务器，其余的中型服务器，等等……处理大量数据需要一些时间(每种数据类型的10k可能需要大约20秒?)，但它似乎可以工作。
您只需要考虑配置少于12台小型服务器(因为您可以用5台中型服务器替换12台小型服务器)和少于27台中型服务器(因为您可以用12台大型服务器替换27台中型服务器)。您可以循环计算小型和中型服务器的数量，然后计算大型服务器的数量为max(0, ceil((need−10 small−24 medium)/54))。
from math import ceil
def cost(cart):
s, m, l = cart
return 68.84 * s + 140.6 * m + 316.09 * l
def cheapest(need):
return min(
(
(s, m, max(0, ceil((need - 10 * s - 24 * m) / 54)))
for s in range(12)
for m in range(27)
),
key=cost,
)