Рубрики

Программа на Python для задачи о ранце 0-1

# Наивная рекурсивная реализация задачи о ранце 0-1

  
# Возвращает максимальное значение, которое можно положить в рюкзак
# мощность Вт

def knapSack(W, wt, val, n):

  

    # Базовый вариант

    if n == 0 or W == 0 :

        return 0

  

    # Если вес n-го предмета больше ранца вместимости

    # W, то этот пункт не может быть включен в оптимальное решение

    if (wt[n-1] > W):

        return knapSack(W, wt, val, n-1)

  

    # вернуть максимум два случая:

    # (1) n-й предмет включен

    # (2) не включены

    else:

        return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),

                   knapSack(W, wt, val, n-1))

  
# конец функции knapSack

  
# Для проверки вышеуказанной функции

val = [60, 100, 120]

wt = [10, 20, 30]

W = 50

n = len(val)

print knapSack(W, wt, val, n)

  
# Этот код предоставлен Nikhil Kumar Singh

Выход:

220

# Динамическое программирование на основе Python
# Программа для задачи о ранце 0-1
# Возвращает максимальное значение, которое может
# положить в рюкзак емкостью W

def knapSack(W, wt, val, n):

    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

  

    # Построить таблицу K [] [] снизу вверх

    for i in range(n + 1):

        for w in range(W + 1):

            if i == 0 or w == 0:

                K[i][w] = 0

            elif wt[i-1] <= w:

                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])

            else:

                K[i][w] = K[i-1][w]

  

    return K[n][W]

  
# Программа драйвера для проверки вышеуказанной функции

val = [60, 100, 120]

wt = [10, 20, 30]

W = 50

n = len(val)

print(knapSack(W, wt, val, n))

  
# Этот код предоставлен Bhavya Jain

Выход:

220

Пожалуйста, обратитесь к полной статье о динамическом программировании | Установите 10 (0-1 Рюкзак Задача) для более подробной информации!

Рекомендуемые посты:

Программа на Python для задачи о ранце 0-1

0.00 (0%) 0 votes