6.4 — Задача о рюкзаке

Представь: у тебя есть рюкзак с ограниченным объёмом. У тебя есть предметы — каждый предмет имеет ценность (насколько он полезный) и объём (сколько места он занимает).

Задача: сложить предметы в рюкзак так, чтобы:

суммарный объём не превышал вместимость рюкзака,
суммарная ценность была максимальной.

Звучит просто, но на самом деле это очень сложная задача. Её даже называют NP-задачей (это значит, что для больших наборов предметов решить её быстро очень трудно).

Но мы можем попробовать перебрать все варианты с помощью битовой арифметики:

бит 1 — предмет кладём в рюкзак,
бит 0 — предмет оставляем.

Таким образом, все возможные наборы предметов — это все двоичные числа от 0 до 2^n - 1, где n — количество предметов.

Пример на Python

#Решение задачи о рюкзаке перебором

items = [(3, 4), (4, 5), (7, 10), (8, 11)]  
# Каждый предмет: (объем, ценность)
capacity = 10  # вместимость рюкзака

best_value = 0
best_set = []

n = len(items)
for mask in range(1 << n):  # перебираем все варианты
    volume = 0
    value = 0
    chosen = []
    for i in range(n):
        if (mask >> i) & 1:  # если бит = 1 → предмет берём
            volume += items[i][0]
            value += items[i][1]
            chosen.append(i)
    if volume <= capacity and value > best_value:
        best_value = value
        best_set = chosen

print("Лучший набор:", best_set)
print("Максимальная ценность:", best_value)

Подмножества

Иногда нужно взять все подмножества множества (например, все группы друзей из класса по 2 человека).

Если у нас есть множество A = {1, 2, 3} и мы хотим все подмножества мощности 2, то получим:

{1, 2},
{1, 3},
{2, 3}.

Это тоже легко сделать через биты:

101 → берём 1 и 3,
110 → берём 1 и 2,
011 → берём 2 и 3.

Перестановки

Перестановка — это все возможные варианты расположения элементов множества.

Например, у множества {1, 2, 3} есть такие перестановки:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Итого у n элементов количество перестановок равно n! (факториал).

Алгоритм Нарайаны (нахождение следующей перестановки)

Есть интересный алгоритм, который позволяет из одной перестановки получить следующую в лексикографическом порядке (как в словаре).

Шаги:

Найти "опорный" элемент (где массив перестаёт уменьшаться).
Найти справа минимальный элемент, больший опорного.
Поменять их местами.
Перевернуть правую часть.

Пример на Python

def next_permutation(seq):
    # 1. найти опорный элемент
    i = len(seq) - 2
    while i >= 0 and seq[i] >= seq[i + 1]:
        i -= 1
    if i == -1:
        return False

    # 2. найти замену опорному
    j = len(seq) - 1
    while seq[j] <= seq[i]:
        j -= 1

    # 3. поменять местами
    seq[i], seq[j] = seq[j], seq[i]

    # 4. перевернуть правую часть
    seq[i + 1:] = reversed(seq[i + 1:])
    return True

#Используем
nums = [1, 2, 3]
while True:
    print(nums)
    if not next_permutation(nums):
        break

Таким образом, мы познакомились с тремя важными задачами:

рюкзак — выбираем лучшие предметы,
подмножества — выбираем группы элементов,
перестановки — переставляем элементы в разные порядки.

Все эти задачи связаны с перебором и битовой арифметикой, и они очень полезны для развития алгоритмического мышления!

Рекурсивный вариант перестановок

Идея алгоритма

Мы берём массив (список) чисел, например [1, 2, 3].
На каждом шаге фиксируем один элемент на месте, а остальные переставляем всеми возможными способами.
Когда в массиве остаётся всего один элемент — это и есть конечный случай. Его переставлять уже не нужно.

Код на Python

def all_permutations(arr, start, end):
    # Базовый случай: если остался только один элемент
    if start == end - 1:
        print(arr)
    else:
        for i in range(start, end):
            # Меняем местами текущий элемент и стартовый
            arr[start], arr[i] = arr[i], arr[start]
            # Вызываем рекурсивно для следующего "куска"
            all_permutations(arr, start + 1, end)
            # Возвращаем элементы обратно (обратный swap)
            arr[start], arr[i] = arr[i], arr[start]

# Пример использования
numbers = [1, 2, 3]
all_permutations(numbers, 0, len(numbers))

Как работает этот код?

В начале мы передаём список и говорим: переставляй его от начала (0) до конца (len(arr)).
Функция переставляет элементы, пока не останется один элемент — тогда она просто выводит список.
После этого программа возвращается назад (это называется шаг возврата рекурсии) и пробует другие перестановки.

Важное замечание

Этот алгоритм действительно печатает все перестановки массива. Но в отличие от итеративного способа, они выводятся не в алфавитном (лексикографическом) порядке, а в том порядке, в котором рекурсия их нашла.

Зато такой метод проще понять и часто используется в задачах по программированию и в олимпиадной информатике.

Задача о рюкзаке