Задача о рюкзаке: разбор решения на Python

Задача о рюкзаке на примере пиратского корабля

Это задача из разряда классических и, конечно, на собеседовании новичку могут предложить решить ее на белой доске. Давайте пройдем решение этой задачи шаг за шагом.

 # Капитан пиратского корабля награбил больше, чем рассчитывал,
 # а грузоподъемность его судна ограничена.
 # Помогите ему найти комбинацию наиболее ценных предметов
 # с учетом того, что на корабль можно загружать
 # не только целые предметы, но и их части.
 # (Т.е. загружаем корабль до полной вместимости,
 # а если какой-то предмет хочется взять, но он не помещается,
 # - забираем его часть).

1. Подготовка

Предположим, у нас есть два массива. В одном содержатся значения веса всех предметов (weights), а в другом — их стоимость (values). Также нам дана грузоподъемность корабля (cap). Все достаточно просто. Давайте определим наш метод:

def knapsack(cap, values, weights):
    pass

2. Стратегия

Подумайте, как бы вы разобрались с этой проблемой, если бы были пиратом. Допустим, вам удалось заполучить кольцо с бриллиантом, которое весит мало, но стоит много, и мешок муки, который весит много, но по сравнению в кольцом стоит мало. Естественно, как нормальный пират, кольцо вы возьмете обязательно, а муки отсыпете столько, сколько у вас места останется.

Исходя из этого, стратегия у нас будет такая:

  1. Отсортируем наш список предметов по их стоимости на единицу веса.
  2. Будем грузить на корабль самые ценные предметы, пока не достигнем предела грузоподъемности.

3. Создаем сортированный список предметов

Сначала мы создадим новый список items, где будут находиться элементы в отсортированном виде. Затем мы переберем в цикле список values (или weights — они все равно имеют одинаковую длину). Для каждого элемента мы будем сохранять его стоимость на единицу веса (value-per-item, vpw), а также вес (зачем он нам нужен, увидите позже).

def knapsack(cap, values, weights):
    items = []
    for i in range(len(values)):
        itemInfo = {
            'vpw': values[i] / weights[i],
            'weight': weights[i]
        }

Далее нам нужно поместить этот элемент в список items. Но мы не можем просто добавить его в конец списка, ведь мы формируем список, отсортированный по vpw. Поэтому, чтобы определить, куда вставить элемент, мы будем обходить список items, сверяя каждый уже имеющийся там vpw с vpw текущего элемента.

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

if len(items) == 0:
    items.append(itemInfo)

В противном случае мы обходим список. Мы не знаем точного числа переходов, которые придется совершить: будем идти по списку до тех пор, пока vpw нашего текущего элемента не окажется меньше, чем vpw элемента в списке. Тут отлично сработает цикл while.

else:
    k = 0
    while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1

Окей, теперь наш индекс k должен указывать на то место, куда нужно вставить новый элемент. Для вставки мы можем воспользоваться методом insert().

else:
    k = 0
    while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1
    items.insert(k, itemInfo)

4. Добавляем элементы из сортированного списка на «корабль»

Пришла пора наполнить корабль грузом. Как уже говорилось, мы собираемся перебирать список предметов, удобно отсортированных по убыванию стоимости, и добавлять эти предметы на корабль, пока не достигнем предела грузоподъемности.

Давайте создадим новые переменные. total — финальная стоимость груза, который удастся увезти на корабле (ее мы будем возвращать). Кроме того, мы создадим переменную cap_left для отслеживания, груз какого веса еще может принять корабль после добавления очередного предмета.

total = 0
cap_left = cap

Теперь давайте переберем наши предметы.

for item in items:

По каждому элементу мы сначала будем проверять, поместится ли он целиком (по весу). Если да — добавляем его стоимость к total (стоимость можно найти путем умножения weight на vpw). Не забудьте вычесть вес предмета из cap_left!

if cap_left - item['weight'] >= 0:
    total += item['weight'] * item['vpw']
    cap_left -= item['weight']

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

Нам нужно проверить, осталось ли место, а затем высчитать, сколько нужно добавить к total. Тут используется математика: мы умножаем vpw элемента, который не помещается полностью, на остаток веса, который еще может принять корабль. После того как мы добавим результат к total, cap_left устанавливается в 0.

elif cap_left > 0:
    total += item['vpw'] * cap_left
    cap_left = 0

Нам остается лишь вернуть total! Все вместе выглядит так:

def knapsack(cap, values, weights):
    items = []
    for i in range(len(values)):
        itemInfo = {
            'vpw': values[i] / weights[i],
            'weight': weights[i]
        }
        if len(items) == 0:
            items.append(itemInfo)
        else:
            k = 0
            while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
                k += 1
            items.insert(k, itemInfo)
    total = 0
    cap_left = cap
    for item in items:
        if cap_left - item['weight'] >= 0:
            total += item['weight'] * item['vpw']
            cap_left -= item['weight']
        elif cap_left > 0:
            total += item['vpw'] * cap_left
            cap_left = 0
    return total

5. Проверяем

Допустим, в нашей добыче есть три предмета: бочка рома, мешок муки и рулон шелка. Вместимость корабля — 60 фунтов.

cap = 60
values = [60, 100, 120]
weights = [20, 50, 30]

print(knapsack(cap, values, weights))

У шелка самый высокий VPW — 4 монеты за фунт. Следующим идет ром (3) и мука (2). Шелк добавляем первым, затем ром. После этого корабль может принять еще 10 фунтов веса: их мы заполняем мукой. 10 фунтов муки стоят 20 монет. Таким образом, общая стоимость добра, которое мы можем увезти на корабле, — 200 монет.

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