Формулировка задачи о рюкзаке

Классическая постановка задачи

Математическая формулировка

Дано:

• Множество предметов n
• Для каждого предмета i известны:
  • Вес w_i
  • Ценность (стоимость) v_i
• Вместимость рюкзака C

Требуется:

Найти такой набор предметов, который:

• Не превышает вместимость рюкзака
• Обеспечивает максимальную суммарную ценность

Формальная запись

Целевая функция:

Максимизировать:

При ограничениях:

1. Ограничение по вместимости:
   ∑_i=1ⁿ w_ix_i ≤ C
2. Ограничения на переменные:
   x_i ∈ {0,1}, i = 1,2,...,n

где x_i — бинарная переменная:

• x_i = 1, если предмет включен в рюкзак
• x_i = 0, если предмет не включен

Варианты задачи

• Базовый вариант (0-1 рюкзак): каждый предмет можно взять не более одного раза
• Неограниченный вариант: предметы можно брать неограниченное количество раз
• Многомерный рюкзак: учитываются несколько ограничений (вес, объем, стоимость)
• Фракционный рюкзак: предметы можно разбивать на части

Аналитическое решение

Метод динамического программирования

Алгоритм решения:

1. Создание таблицы M[i,j], где:
• i — номер предмета
• j — текущий вес рюкзака
2. Заполнение таблицы по формуле:
   M[i,j] = max(M[i-1,j], v_i + M[i-1,j-w_i])
3. Базовые случаи:
   • M[0,j] = 0 для всех j
   • M[i,0] = 0 для всех i

Шаги решения:

• Инициализация массива M
• Последовательное заполнение таблицы
• Восстановление решения из таблицы

Временная сложность:

Алгоритм работает за время O(nC), где:

• n — количество предметов
• C — вместимость рюкзака

Пример реализации:

function knapsack(values, weights, n, C):
    create array M[n+1][C+1]
    
    for i from 0 to n:
        M[i][0] = 0
    
    for j from 0 to C:
        M[0][j] = 0
    
    for i from 1 to n:
        for j from 1 to C:
            if weights[i] <= j:
                M[i][j] = max(M[i-1][j], values[i] + M[i-1][j-weights[i]])
            else:
                M[i][j] = M[i-1][j]
    
    return M[n][C]
        

Особенности применения:

• Метод эффективен для задач среднего размера
• Требует большого объема памяти
• Гарантирует нахождение оптимального решения