Задача о рюкзаке — широко известная задача оптимизации в информатике. Учитывая набор предметов, каждый из которых имеет вес и ценность, цель состоит в том, чтобы определить наиболее ценную комбинацию предметов, которая поместится в рюкзак с ограниченной грузоподъемностью. В этой статье мы рассмотрим различные методы на основе таблиц для эффективного решения задачи о рюкзаке. Мы предоставим примеры кода для каждого метода, чтобы помочь вам понять и реализовать их.

1. Задача о рюкзаке 0/1:
   Задача о рюкзаке 0/1 — это самый простой вариант задачи о рюкзаке. В этой версии каждый предмет можно выбрать в рюкзаке только один раз (либо включить, либо исключить). Вот пример реализации на Python:

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[n][capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
max_value = knapsack_01(weights, values, capacity)
print("Maximum value:", max_value)

2. Задача о неограниченном рюкзаке:
   В задаче о неограниченном рюкзаке нет ограничений на количество раз, когда предмет можно выбрать. Вот пример реализации на Python:

def unbounded_knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(capacity + 1):
        for j in range(n):
            if weights[j] <= i:
                dp[i] = max(dp[i], values[j] + dp[i - weights[j]])
    return dp[capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
max_value = unbounded_knapsack(weights, values, capacity)
print("Maximum value:", max_value)

3. Задача об ограниченном рюкзаке:
   Задача об ограниченном рюкзаке — это вариант, в котором существует ограничение на максимальное количество раз, которое можно выбрать предмет. Вот пример реализации на Python:

def bounded_knapsack(weights, values, capacity, counts):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for j in range(capacity, weights[i] - 1, -1):
            for k in range(1, min(counts[i] + 1, (j // weights[i]) + 1)):
                dp[j] = max(dp[j], values[i] * k + dp[j - k * weights[i]])
    return dp[capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
counts = [2, 1, 3, 2]
max_value = bounded_knapsack(weights, values, capacity, counts)
print("Maximum value:", max_value)

Методы на основе таблиц обеспечивают эффективное решение задачи о рюкзаке за счет использования методов динамического программирования. В этой статье мы исследовали три варианта задачи о рюкзаке: рюкзак 0/1, неограниченный рюкзак и ограниченный рюкзак. Мы предоставили примеры кода на Python для каждого метода. Поняв эти методы, вы теперь сможете эффективно решать проблемы с рюкзаками в своих проектах.