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

Question

我有一个 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 秒？)，但它似乎有效。

Answer 1

您只需考虑少于 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,
    )