Выбор минимального количества машин, которые суммируются для удовлетворения производственного результата - Упростите код? - PullRequest
Новая
       26

Выбор минимального количества машин, которые суммируются для удовлетворения производственного результата - Упростите код?

0 голосов
/ 27 марта 2020

Я пытаюсь определить минимальное количество «машин», которые могут удовлетворить определенный объем производства. По «большому правилу», более крупная машина является более экономичным выбором, чем более мелкая. Я считаю, что это можно сформулировать как проблему оптимизации или решить с помощью какого-то алгоритма, который мне неизвестен. Если есть, буду признателен за указатели (какой алгоритм реализовать). Если нет, то мне было интересно, есть ли более простой и элегантный способ решения проблемы. Я думал, что может быть вариант с использованием математических наборов, объектов числовой линии и т. Д. c.

нижний = (нижний [i], верхний [i]) определяет диапазон выпуска продукции для машины i. Индекс i определяет машину в OrderedDict вне этой проблемы. Ie последний индекс соответствует последнему элементу в словаре. Эта функция вернет список машин, которые я затем смогу реализовать с помощью 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

1 Ответ

1 голос
/ 27 марта 2020

Вот решение 

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

Это отличается от вашего существующего решения target из 0 или 16+. Я считаю, что в обоих случаях мое решение строго лучше.

...