Fractional Knapsack

Q: Какова временная сложность задачи о дробном рюкзаке?

Сортировка предметов по ценности на единицу веса требует O(n log n) , а заполнение выполняется за один проход, поэтому общая сложность составляет O(n log n) при использовании O(n) памяти для порядка. Поиск предмета с наибольшей плотностью на каждом шаге требует O(n²) .

Q: Как решить задачу о дробном рюкзаке без чисел с плавающей точкой?

При положительных весах a / b > c / d — это та же проверка, что и a × d > c × b , поэтому сравнивайте плотности перекрёстным умножением. Лучшее значение — это целое число плюс одна дробь, values[i] × room / weights[i] для разрезаемого предмета, поэтому одного целочисленного деления достаточно, чтобы получить точный ответ с округлением вниз.

СреднеЖадные алгоритмы Сортировка

+10

У тебя есть n предметов. Предмет i стоит values[i] и весит weights[i]. Вместимость твоей сумки — не более capacity, и ты можешь взять любую часть предмета: часть предмета i весом w стоит values[i] × w / weights[i].

Напиши функцию с именем fractionalKnapsack, которая возвращает наибольшую общую стоимость, которую можно поместить в сумку, округлённую вниз до целого числа.

Функция

fractionalKnapsack(values: integer-array, weights: integer-array, capacity: integer) → integer

valuesinteger-array: ценность каждого предмета
weightsinteger-array: вес каждого предмета
capacityinteger: максимальный вес, который может выдержать сумка
Возвращаетinteger: наибольшая общая ценность, которая помещается в рюкзак, округлённая вниз

Ограничения

1 ≤ n ≤ 5000, где n = values.length = weights.length
1 ≤ values[i], weights[i] ≤ 10⁴
1 ≤ capacity ≤ 10⁸

Примеры

Ввод: values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
Вывод: 151
Пояснение: На единицу веса предметы стоят 5, 3, 6 и 2.5. Предметы 2 и 0 помещаются целиком и дают 70, остаётся место для 27, а 27 из 30 единиц предмета 1 добавляют 81, итого 151.

Ввод: values = [10, 7]weights = [4, 3]capacity = 5
Вывод: 12
Пояснение: Ценность единицы предмета 0 составляет 2.5, а предмета 1 — около 2.33, поэтому предмет 0 помещается целиком и приносит 10. Одна из 3 единиц предмета 1 добавляет 7 / 3, а 12 и одна треть округляется вниз до 12.

Дополнительный вопрос

Можешь найти ответ за время O(n), не сортируя все элементы?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Выбирайте самый плотный предмет на каждом шаге

Верно, но не успевает на самых больших тестах

Идея

Заполняй рюкзак, начиная с предмета с наибольшей плотностью: бери его целиком, если он помещается, иначе бери часть, которая заполнит рюкзак, и остановись. Находи самый плотный из неиспользованных предметов, просматривая их все и сравнивая values[i] × weights[j] с values[j] × weights[i] вместо деления. При положительных весах это равносильная проверка, и оба произведения не превышают 10^8.

Сначала брать самые плотные предметы — оптимальный подход: если в рюкзаке есть часть менее плотного предмета, а более плотный предмет ещё не взят целиком, замена этой части на более плотный предмет не уменьшит ценность. Продолжай делать такие замены — и получишь загрузку из предметов в порядке убывания плотности.

В каждом из максимум n раундов просматриваются неиспользованные предметы; всего получается около n²/2 = 12.5 миллиона сравнений при n = 5000.

Алгоритм

Пометь каждый предмет как неиспользованный и установи room = capacity и total = 0.
Пока есть место, просматривай неиспользованные предметы и выбирай предмет с наибольшей плотностью, сравнивая плотности перекрёстным умножением.
Если предметов не осталось, остановись. Иначе пометь выбранный предмет как использованный.
Если он помещается, добавь его значение к total, а его вес вычти из room. Если он не помещается, прибавь values[i] × room / weights[i] с целочисленным делением и остановись.
Верни total.

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    used = [False] * n
    total = 0
    room = capacity
    while room > 0:
        best = -1
        for i in range(n):
            # i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
            if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
                best = i
        if best == -1:
            break  # every item is already in the bag
        used[best] = True
        if weights[best] <= room:
            total += values[best]
            room -= weights[best]
        else:
            total += values[best] * room // weights[best]  # the part that fits, rounded down
            room = 0
    return total

Сортировать по ценности на единицу веса

Идея

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

Бери предметы целиком, пока они помещаются. Первый предмет, который не помещается, — единственный, который нужно разделить: он добавляет values[i] × room / weights[i], а целочисленное деление округляет результат вниз. Все предметы до него берутся целиком, поэтому округление этого слагаемого даёт точный ответ. Сортировка занимает O(n log n), а проход — O(n).

Алгоритм

Составь список индексов предметов и отсортируй их по плотности, от большей к меньшей, используя сравнение с перекрёстным умножением.
Установи room = capacity и total = 0.
Для каждого предмета в этом порядке, если weights[i] ≤ room, прибавь его ценность и вычти его вес из room.
Иначе прибавь values[i] × room / weights[i] с целочисленным делением и остановись.
Верни total.

from functools import cmp_to_key


def fractionalKnapsack(values, weights, capacity):
    # a goes before b when values[a] / weights[a] > values[b] / weights[b],
    # tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
    def denser_first(a, b):
        return values[b] * weights[a] - values[a] * weights[b]

    order = sorted(range(len(values)), key=cmp_to_key(denser_first))
    total = 0
    room = capacity
    for i in order:
        if weights[i] <= room:
            total += values[i]  # the whole item fits
            room -= weights[i]
        else:
            total += values[i] * room // weights[i]  # the part that fits, rounded down
            break
    return total

Ловушки и крайние случаи

Сортировка только по стоимости или только по весу. В первом примере предмет стоимостью 90 занимает лишь третье место по плотности; если взять его первым, останется место для половины предмета стоимостью 50, и получится 115 вместо 151.
Деление перед умножением. При стоимости 13, весе 7 и свободной вместимости 3 выражение 13 / 7 * 3 в целочисленной арифметике даёт 3, а 13 * 3 / 7 даёт правильное значение 5.
Ожидание, что предмет каждый раз придётся разрезать. В третьем примере помещаются все предметы, и ответ равен сумме их стоимостей — 13.

Частые вопросы3

Какова временная сложность задачи о дробном рюкзаке?

Сортировка предметов по ценности на единицу веса требует O(n log n), а заполнение выполняется за один проход, поэтому общая сложность составляет O(n log n) при использовании O(n) памяти для порядка. Поиск предмета с наибольшей плотностью на каждом шаге требует O(n²).

Почему жадный алгоритм работает для задачи о дробном рюкзаке, но не для задачи о рюкзаке 0/1?

Дробление позволяет заменить часть веса менее ценного предмета на более ценный. Без дробления более ценный предмет может оставить место, которое ничем другим не заполнить. При значениях 8, 11, 15, весах 2, 3, 4 и вместимости 7 выбор сначала предметов с наибольшей плотностью даёт веса 2 и 4, то есть 23, а веса 3 и 4 дают 26. Для версии 0/1 требуется динамическое программирование.

Как решить задачу о дробном рюкзаке без чисел с плавающей точкой?

При положительных весах a / b > c / d — это та же проверка, что и a × d > c × b, поэтому сравнивайте плотности перекрёстным умножением. Лучшее значение — это целое число плюс одна дробь, values[i] × room / weights[i] для разрезаемого предмета, поэтому одного целочисленного деления достаточно, чтобы получить точный ответ с округлением вниз.

def fractionalKnapsack(values, weights, capacity):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

values = [40, 90, 30, 50]
weights = [8, 30, 5, 20]
capacity = 40

Ожидаемый вывод