Задача о рюкзаке 0/1: реализация и оптимизация

Расширенные примеры решения задачи о рюкзаке 0/1

Восстановление набора выбранных предметов

После нахождения максимальной ценности часто требуется узнать, какие предметы были взяты. Для этого используется двумерная таблица dp. Алгоритм: начинаем с dp[n][capacity], если dp[i][j] != dp[i-1][j], значит i-й предмет взят, уменьшаем j на его вес и переходим к i-1.

def knapsack_with_items(weights, values, capacity):
    n = len(weights)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        w = weights[i-1]
        v = values[i-1]
        for j in range(1, capacity+1):
            if j >= w:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
            else:
                dp[i][j] = dp[i-1][j]
    # Восстановление
    items = []
    j = capacity
    for i in range(n, 0, -1):
        if dp[i][j] != dp[i-1][j]:
            items.append(i-1)
            j -= weights[i-1]
    return dp[n][capacity], items[::-1]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
max_val, chosen = knapsack_with_items(weights, values, capacity)
print("Максимальная ценность:", max_val)
print("Номера предметов:", chosen)

Максимальная ценность: 9
Номера предметов: [0, 1, 3]

Сравнение производительности решений

Для случайных данных с n=100, capacity=1000 измерим время и память.

import random, time, sys

n, capacity = 100, 1000
weights = [random.randint(1, 100) for _ in range(n)]
values = [random.randint(1, 100) for _ in range(n)]

def time_it(func, *args):
    start = time.perf_counter()
    result = func(*args)
    return result, time.perf_counter() - start

# двумерный
res2d, t2d = time_it(knapsack_2d, weights, values, capacity)
# одномерный
res1d, t1d = time_it(knapsack_1d, weights, values, capacity)
# рекурсивный с мемо (возможно долго - ограничим)
if n <= 30:
    res_rec, t_rec = time_it(knapsack_rec, weights, values, capacity)
else:
    res_rec, t_rec = None, None

print(f"2D DP: {t2d:.4f} сек, ответ {res2d}")
print(f"1D DP: {t1d:.4f} сек, ответ {res1d}")
if t_rec:
    print(f"Recursive: {t_rec:.4f} сек, ответ {res_rec}")

2D DP: 0.0152 сек, ответ 985
1D DP: 0.0081 сек, ответ 985

Одномерный вариант быстрее из-за меньшего количества операций и лучшей локальности данных. Рекурсия медленнее и имеет накладные расходы на вызовы функций и кэш.

Использование functools.lru_cache для мемоизации

В рекурсивном решении lru_cache автоматически запоминает результаты для пар (i, cap). Это удобно, но стоит помнить о переполнении стека при больших n.

from functools import lru_cache

def knapsack_lru(weights, values, capacity):
    @lru_cache(maxsize=None)
    def dfs(idx, cap):
        if idx == len(weights) or cap == 0:
            return 0
        if weights[idx] > cap:
            return dfs(idx+1, cap)
        return max(dfs(idx+1, cap), dfs(idx+1, cap - weights[idx]) + values[idx])
    return dfs(0, capacity)

Пример вызова:

print(knapsack_lru([2,3,4],[3,4,5],5))  # Вывод: 7 (предметы 0 и 1)

7

Обработка нецелых весов с помощью масштабирования

Если веса вещественные, их можно умножить на коэффициент (например, 100) и округлить, но это может исказить точность. Альтернатива - использовать алгоритм для дробного рюкзака или метод ветвей и границ.

def knapsack_float_approx(weights, values, capacity, scale=100):
    int_weights = [int(round(w * scale)) for w in weights]
    int_capacity = int(round(capacity * scale))
    return knapsack_1d(int_weights, values, int_capacity)

Погрешность зависит от scale. Увеличение scale приводит к росту памяти.