选择总计满足生产输出的最少机器数量 - 简化代码？

Question

我正在尝试确定满足特定产量的最小 "machines" 数量。 "rule-of-thumb"，大机器比小机器更经济。我相信这可以表述为优化问题或使用我不知道的某种算法来解决。如果有，我将不胜感激（要实现哪种算法）。如果没有，我想知道是否有更简单、更优雅的方法来解决这个问题。我在想可能有一个使用数学集、数轴对象等的选项。

lower = (lower[i],upper[i]) 定义机器 i 的生产输出范围。索引 i 在这个问题之外的 OrderedDict 中定义了机器。即最后一个索引对应字典中的最后一项。此函数将 return 一个机器列表，其中然后我可以使用 OrderedDict（它包含机器上的其他信息）来实现。

排除错误检查以简化代码。


lower = [0, 5, 10]
upper = [3, 9, 15]

他们需要的一些用户定义的生产价值

prod_value = 4

假设所有生产输出都是整数并且允许不连续（4 不在任何机器范围内）

def get_machines(prod_value, lower, upper):

        prod_value = prod_value
        lower = lower
        upper = upper

        def in_range(prod_value, lower, upper):
                # Function that returns (machine index, machine output) if it is not greater than max

                for i in range(len(lower)):
                        # within range

                        if prod_value >= lower[i] and prod_value <= upper[i]:

                            return (i,prod_value)

                        # This catches all machines smaller than min or discontinuities 

                        elif prod_value <= lower[i]:

                            return (i, lower[i])
                        else:
                            continue

        machine_list = []

        if prod_value > upper[-1]:

                while prod_value:

                        if prod_value - upper[-1] > 0:

                                prod_value -= upper[-1]

                                machine_list.append((-1,upper[-1]))
                        else:
                                machine_list.append(in_range(prod_value,lower,upper))

                                prod_value = 0 

                return machine_list

        else:
                machine_list.append(in_range(prod_value,lower,upper))   

                return machine_list

Answer 1

这是一个解决方案

import collections
Solution = collections.namedtuple(
            'Solution', 'machine_type production machines previous overproduction')

def optimal_machines (target, lower, upper):
    best = [None for i in range(target+1)]
    best[0] = Solution(
                machine_type=None, production=None, machines=0,
                previous=None, overproduction=0)
    for i in range(target):
        if best[i] is not None:
            soln = best[i]
            for j in range(len(lower)):
                for production in range(upper[j]+1):
                    k = i+production
                    if target < k:
                        break
                    overproduction = soln.overproduction
                    if production < lower[j]:
                        overproduction += lower[j] - production
                        production = lower[j]
                    if best[k] is None or (soln.machines+1, overproduction) < (best[k].machines, best[k].overproduction):                            
                        best[k] = Solution(
                                    machine_type=j, production=production,
                                    machines=best[i].machines+1, previous=best[i],
                                    overproduction=overproduction)

    # We now have the answer as a linked list.  Convert that to the desired format.
    answer = []
    solution = best[target]
    if solution is None:
        return None
    else:
        while solution.machine_type is not None:
            answer.append([solution.machine_type, solution.production])
            solution = solution.previous
        return answer

这与 0 或 16+ 的现有解决方案 target 不同。我相信在这两种情况下我的解决方案都更好。

选择总计满足生产输出的最少机器数量 - 简化代码？

Selecting Minimum Number of Machines that Sum to Meet A Production Output - Simplify Code?

python

algorithm

math

simplify

data-structures