Две версии алгоритма программирования Dynami c для задачи о ранце - PullRequest
Новая
       89

Две версии алгоритма программирования Dynami c для задачи о ранце

0 голосов
/ 29 апреля 2020

У меня есть две разные версии алгоритма программирования Dynami c в Python, которые используются для задач ранца. Я пытаюсь решить, какой код является более эффективным и почему. Также я пытаюсь рассказать, какой метод для создания каждого кода был. 

ef DPKP(v, s, C):
#Applies the dynamic programming method to the knapsack problem where v are the values of the n items, s are the sizes of the n items, and C is the capacity.  \
n = len(v)
V = [ [0 for cp in range(C+1)] for j in range (n)  ]
X = [ [0 for cp in range(C+1)] for j in range (n)  ]

for cp in range(C+1):
    if s[n-1] <= cp:
        V[n-1][cp] = v[n-1]
        X[n-1][cp] = 1

for i in reversed(range(n-1)):
    for cp in range(C+1):
        if s[i] <= cp:
            if v[i] + V[i+1][cp-s[i]] > V[i+1][cp]:
                V[i][cp] = v[i] + V[i+1][cp-s[i]]
                X[i][cp] = 1
            else:
                V[i][cp] = V[i+1][cp]
        else:
            V[i][cp] = V[i+1][cp]

return V, X

def DPKP1(v, s, C):
'''Applies the dynamic programming method to the knapsack problem
where v are the values of the n items, s are the sizes of the n items, 
and C is the capacity.  '''

n = len(v)
V = [ [] for j in range (n)  ]
X = [ [] for j in range (n)  ]

for cp in range(C+1):
    if s[n-1] <= cp:
        V[n-1].append(v[n-1])
        X[n-1].append(1)
    else:
        V[n-1].append(0)
        X[n-1].append(0)  

for i in reversed(range(n-1)):
    for cp in range(C+1):
        if s[i] <= cp:
            if v[i] + V[i+1][cp-s[i]] > V[i+1][cp]:
                V[i].append(v[i] + V[i+1][cp-s[i]])
                X[i].append(1)
            else:
                V[i].append(V[i+1][cp])
                X[i].append(0)
        else:
            V[i].append(V[i+1][cp])
            X[i].append(0)

return V, X

Пока единственное отличие, которое я могу сказать, состоит в том, что DPKP1 использует append, а DPKP немного быстрее тестируется с использованием timeit.timet ().

...