Это задача из разряда классических и, конечно, на собеседовании новичку могут предложить решить ее на белой доске. Давайте пройдем решение этой задачи шаг за шагом.
# Капитан пиратского корабля награбил больше, чем рассчитывал, # а грузоподъемность его судна ограничена. # Помогите ему найти комбинацию наиболее ценных предметов # с учетом того, что на корабль можно загружать # не только целые предметы, но и их части. # (Т.е. загружаем корабль до полной вместимости, # а если какой-то предмет хочется взять, но он не помещается, # - забираем его часть).
1. Подготовка
Предположим, у нас есть два массива. В одном содержатся значения веса всех предметов (weights), а в другом — их стоимость (values). Также нам дана грузоподъемность корабля (cap). Все достаточно просто. Давайте определим наш метод:
def knapsack(cap, values, weights):
pass
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 монет.
Эта задача имеет много способов решения, мы разобрали лишь один из них.
