gpt4 book ai didi

python - 箱装/背包变化 : Fitting discrete data into discrete servers

转载 作者:行者123 更新时间:2023-12-04 14:53:18 25 4
gpt4 key购买 nike

我有一个 Python 编码任务似乎是装箱问题或背包问题的某种变体,我不完全确定。我有一个似乎可行的选项,但我不认为它本身是正确的解决方案,因为可能存在可能失败的边缘情况。 (我不是 CS 或数学专业的学生,​​所以我在算法/组合学方面的知识非常初级。)

问题

用户可以选择 3 种数据类型的配置:

  • 数据为 1 GB
  • 数据为 1.5 GB
  • 数据为 2 GB

控制台应用程序会依次询问:“您需要多少小件?中号?大号?”。我需要将这些数据放入最便宜的服务器配置中:

  • 小型服务器容量为 10 GB,价格为 68.84 美元
  • 中型服务器容量为 24 GB,费用为 140.60 美元
  • 大型服务器拥有 54 GB,成本 316.09 美元

因此,例如,如果用户选择总共 20 GB 的数据,该函数应注意使用 2 台小型服务器比使用 1 台中型服务器更便宜。

我编写的函数主要使用除法来查找整数,并在适当的地方使用 floor/ceil 调用。我编写的 block 按顺序通过只有 L 个服务器的配置,然后是 L 和 M,然后是 L、M 和 S,等等。

函数如下:

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

我感觉这里有问题。例如,当我输入 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,
)

关于python - 箱装/背包变化 : Fitting discrete data into discrete servers,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68650394/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com