Проблема рюкзака с повторяющимися компонентами для наименьшего значения, чтобы заполнить (или немного больше) в Python - PullRequest
Новая
       30

Проблема рюкзака с повторяющимися компонентами для наименьшего значения, чтобы заполнить (или немного больше) в Python

2 голосов
/ 06 ноября 2019

Я на самом деле пытаюсь найти самую низкую стоимость поставки нестандартных доз лекарств из флаконов - однако во время исследования я обнаружил, что проблема с рюкзаком - лучший способ описать проблему в том виде, в котором она в настоящее время понимается.

Разбивка проблемы * Доза назначается в зависимости от клинической необходимости. * Затем рассматриваются коммерчески доступные флаконы для составления дозы (и соответствующей дозы). Флакон одного размера можно использовать более одного раза. * Комбинация флакон / размер может обеспечить избыток (то есть обеспечить более высокую дозу, чем требуется) - так как эта комбинация работает дешевле, чем удовлетворение самой дозы или предоставление меньшего избытка. Поэтому допускается избыток или потери при условии, что комбинации дают предписанную дозу, даже если есть потери. * В выходных данных должны отображаться используемая комбинация кол-во / флакон и стоимость этих комбинаций.

Примером доступных флаконов являются 50 мг по цене 15 долларов США, 100 мг по цене 32 доллара США и 200 мг по цене 64

Допустим, чтодоза 220 мг предписана. Ниже приведены некоторые возможные варианты составления дозы (помните, что количество отходов не имеет значения, если оно обеспечивает самый дешевый вариант составления требуемой дозы. 

5 x 50mg = 250mg (30mg over) = $75
3 x 50mg + 1 x 100mg = 250mg (30mg over) = $77
2 x 100mg + 1 x 200mg = 400mg (180mg over) = $128
1 x 50mg + 1 x 200mg = 250mg (30mg over) = $79
3 x 100mg = 300mg (80mg over) = $96

Таким образом, мы можем видетьчто самый дешевый вариант - это row1 5x50 мг за 75

Если бы кто-нибудь мог указать мне правильное направление, я был бы признателен!

Приведенный ниже код использует каждый компонент только один раз, но яЯ заблудился о том, как изменить, чтобы заставить их перерабатывать их. 

items = [("ITEM01", 100, 10000), ("ITEM02", 24, 576), \
    ("ITEM03", 24, 576), ("ITEM04", 51, 2500), ("ITEM05", 155, 25)]
S = sum([item[1] for item in items])    #sums all the weights in the list of items
dp = [None for i in range(S + 1)]       #list within which cycles through each integer of weights creates a list of "None,"
dp[0] = []                              #removes the first none from the list

for item in items:                      #for each element in the list of available vials
    for i in range(S, -1, -1):          #counts down from sum of all weights of available vial sizes DOWN TO zero (0) 
        if dp[i] is not None and i + item[1] <= S and \     
    (                                                               #if the long list of Nones - does not read None
        dp[i + item[1]] is None
        or
        sum(set_item[2] for set_item in dp[i]) + item[2]
            > sum(set_item[2] for set_item in dp[i + item[1]])
    ):
            dp[i + item[1]] = dp[i] + [item]

desired_sum = 200                   #desired weight 
i = j = desired_sum                 # desired sum becomes i and it also becomes j

while i >= 0 and j <= S:            #while desired sum(i) is over 0 and less then sum of weight of all vials in the list.
    if dp[i] is not None:           #if the none list entry at that point is NOT none
        print (dp[i])               #print element from that list that isn't 'None'
        break
    elif dp[j] is not None:         #if None list at desired_weight index is not None
        print (dp[j])               #print the element that isn't none
        break
    else:
        i -= 1                      #else diverge i and j which are originally the same
        j += 1
...