Запись из дневника доктора Ватсона

1. Тревожный звонок

Был хмурый лондонский вечер, когда в нашу скромную квартиру на Бейкер-стрит ворвался взволнованный инспектор Лестрейд.

— Холмс! Нам срочно нужна ваша помощь! — воскликнул он, сбрасывая с плеч дождевик. — В городе орудует хитрый вор. Он крадёт предметы, но уносит их только в одном рюкзаке ограниченной вместимости. Нам нужно вычислить, какие именно вещи он унесёт, чтобы максимизировать свою добычу!

Шерлок поднял бровь.

— Задача о рюкзаке… Классика. Лестрейд, вы принесли данные?

— Да! Вот список украденных предметов с их весом и стоимостью!

Холмс бросил взгляд на листок:

— Вместимость рюкзака — 6 кг, — добавил Лестрейд.

2. SQL вступает в игру

Холмс ухмыльнулся.

— Ватсон, достаньте мой ноутбук. Мы решим это с помощью SQL.

Я удивился:

— Но, Холмс, разве это не задача для динамического программирования?

— Конечно, но давайте посмотрим, как её можно неправильно решить на SQL, а потом найдём оптимальный способ.

2.1. Наивный подход: перебор всех комбинаций

WITH RECURSIVE all_combinations AS (
    SELECT 
        0 AS total_weight,
        0 AS total_value,
        '' AS items
    UNION ALL
    SELECT 
        ac.total_weight + i.weight,
        ac.total_value + i.value,
        ac.items || ', ' || i.item
    FROM all_combinations ac
    JOIN items i ON i.item NOT IN (SELECT unnest(string_to_array(ac.items, ', ')))
    WHERE ac.total_weight + i.weight <= 6
)
SELECT * FROM all_combinations
WHERE total_weight <= 6
ORDER BY total_value DESC
LIMIT 1;

— Временная сложность: O(2ⁿ) — ужасно! — воскликнул я.

— Именно, Ватсон. Этот запрос перебирает все возможные комбинации, что для большого набора данных превратится в кошмар.

WITH ranked_items AS (
    SELECT 
        item,
        weight,
        value,
        value / weight AS value_density,
        ROW_NUMBER() OVER (ORDER BY value / weight DESC) AS rank
    FROM items
),
knapsack AS (
    SELECT 
        item,
        weight,
        value,
        SUM(weight) OVER (ORDER BY rank) AS cumulative_weight,
        SUM(value) OVER (ORDER BY rank) AS cumulative_value
    FROM ranked_items
    WHERE SUM(weight) OVER (ORDER BY rank) <= 6
)
SELECT * FROM knapsack
WHERE cumulative_weight <= 6
ORDER BY cumulative_value DESC

— Лучше, но не идеально, — заметил я. — Это жадный алгоритм, который может дать неоптимальный результат.

— Верно, Ватсон. Настоящий воришка не будет брать просто самые ценные вещи — он выберет оптимальную комбинацию.

2.3. Идеальное решение: CTE + перебор с ограничением

— Тогда давайте ограничим глубину рекурсии и добавим мемоизацию.

WITH RECURSIVE knapsack AS (
    SELECT 
        0 AS total_weight,
        0 AS total_value,
        ARRAY[]::TEXT[] AS items
    UNION ALL
    SELECT 
        k.total_weight + i.weight,
        k.total_value + i.value,
        k.items || i.item
    FROM knapsack k
    JOIN items i ON i.item > ALL(k.items)  -- избегаем повторов
    WHERE k.total_weight + i.weight <= 6
)
SELECT * FROM knapsack
WHERE total_weight <= 6
ORDER BY total_value DESC
LIMIT 1;

— O(n²), уже неплохо, — пробормотал я.

— Но всё равно не динамическое программирование, — вздохнул Холмс.

3. Мораль для начинающих разработчиков

Лестрейд, потрясённый, спросил:

— Так как же всё-таки правильно решать такие задачи?

Холмс откинулся в кресле.

— 1. Не доверяйте слепо ИИ. ChatGPT или Copilot могут предложить наивный SQL-запрос, который убьёт вашу базу данных.
— 2. Вникайте в алгоритмическую сложность. Если задача NP-трудная (как рюкзак), SQL — не лучший инструмент.
— 3. Выбирайте правильный подход. Динамическое программирование на Python решит задачу за O(n·W), а не за O(2ⁿ).

— Но… а что насчёт ИИ? — робко спросил Лестрейд.

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

4. Развязка

В итоге мы нашли оптимальный набор: фарфор (3кг, £300) + книга (2кг, £150) + подсвечник (1кг, £100) = £550.

Лестрейд арестовал вора, а Холмс, довольный, закурил трубку.

— Мораль? Прежде чем писать код, подумайте. Иначе ваш запрос станет преступлением против производительности.

Конец записи.

? P.S. Если ваш SQL-запрос выполняется дольше, чем расследование Холмса, — пора пересмотреть подход.