Последним алгоритмом, который нам пришлось кодировать в Алгоритмах 2, была проблема ранца, которая заключается в следующем:
Проблема рюкзака или проблема рюкзака — это проблема комбинаторной оптимизации: учитывая набор предметов, каждый из которых имеет вес и значение, определяют количество каждого предмета, включаемого в коллекцию, чтобы общий вес был меньше или равен данный лимит и общее значение максимально велико.
Мы внесли небольшие изменения в это в том, что вы можете выбрать каждый предмет только один раз, что называется проблемой ранца 0-1.
В нашем случае нам был предоставлен входной файл, из которого вы можете получить размер рюкзака, общее количество предметов и индивидуальные веса и значения каждого из них.
Псевдокод версии алгоритма, который использует 2D-массив как часть решения динамического программирования, выглядит следующим образом:
- Пусть A = 2-D массив размером n (количество предметов) * W (размер рюкзака)
- Инициализация A [0, X] = 0 для X = 0,1, .., W
- для i = 1,2,3,… n
- для х = 0,1,2,…, ш
- A [i, x] = max {A [i-1, x], A [x-1, xw i ] + V i }
- где V i — это значение i- го элемента, а W i — вес i- го элемента.
- для х = 0,1,2,…, ш
- вернуть A [n, W]
Эта версия работает в O (nW) времени и O (nW) пространстве. Это основная часть моего решения для Ruby :
number_of_items,knapsack_size = # calculated from file
cache = [].tap { |m| (number_of_items+1).times { m << Array.new(knapsack_size+1) } }
cache[0].each_with_index { |value, weight| cache[0][weight] = 0 }
(1..number_of_items).each do |i|
value, weight = rows[i-1]
(0..knapsack_size).each do |x|
if weight > x
cache[i][x] = cache[i-1][x]
else
cache[i][x] = [cache[i-1][x], cache[i-1][x-weight] + value].max
end
end
end
p cache[number_of_items][knapsack_size]
Этот подход работает достаточно хорошо, когда n и W малы, но во второй части проблемы n было 500, а W было 2 000 000, что означает, что двумерный массив будет содержать 1 миллиард записей.
Если в этой структуре данных мы храним целые числа по 4 байта каждый, то требуемый объем памяти составляет 3,72 ГБ — это слишком много для моей машины!
Вместо этого, лучшей структурой данных будет та, в которой нам не нужно выделять все заранее, а можно просто заполнить ее по ходу дела. В этом случае мы все еще можем использовать массив для количества элементов, но вместо хранения другого массива в каждом слоте мы будем использовать словарь / хэш-карту.
Если мы возьмем подход «снизу вверх» к этой проблеме, то, похоже, мы в конечном итоге решим множество подзадач, которые не имеют отношения к нашему окончательному решению, поэтому я решил попробовать рекурсивный подход «сверху вниз», и вот чем я закончил:
@new_cache = [].tap { |m| (@number_of_items+1).times { m << {} } }
def knapsack_cached(rows, knapsack_size, index)
return 0 if knapsack_size == 0 || index == 0
value, weight = rows[index]
if weight > knapsack_size
stored_value = @new_cache[index-1][knapsack_size]
return stored_value unless stored_value.nil?
return @new_cache[index-1][knapsack_size] = knapsack_cached(rows, knapsack_size, index-1)
else
stored_value = @new_cache[index-1][knapsack_size]
return stored_value unless stored_value.nil?
option_1 = knapsack_cached(rows, knapsack_size, index-1)
option_2 = value + knapsack_cached(rows, knapsack_size - weight, index-1)
return @new_cache[index-1][knapsack_size] = [option_1, option_2].max
end
end
p knapsack_cached(rows, @knapsack_size, @number_of_items-1)
Код очень похож на предыдущую версию, за исключением того, что мы начинаем с последнего пункта и продолжаем наш путь внутрь. Мы закончили тем, что сохранили 2 549 110 элементов в @new_array, которые мы можем обработать , выполнив это:
p @new_cache.inject(0) { |acc,x| acc + x.length}
Если бы мы использовали двумерный массив, это означало бы, что мы заполнили бы только 0,25% структуры данных, действительно расточительно!
Я хотел немного рассказать о том, насколько быстро этот алгоритм работает в Ruby по сравнению с JRuby, и недавно я наткнулся на nailgun — который позволяет вам запускать постоянную JVM, а затем запускать свой код через него вместо запуска нового. каждый раз, так что я думал, что смогу поиграть с этим!
# Ruby $ time ruby knapsack/knapsack_rec.rb real 0m18.889s user 0m18.613s sys 0m0.138s # JRuby $ time ruby knapsack/knapsack_rec.rb real 0m6.380s user 0m10.862s sys 0m0.428s # JRuby with nailgun $ ruby --ng-server & # start up the nailgun server $ time ruby --ng knapsack/knapsack_rec.rb real 0m6.734s user 0m0.023s sys 0m0.021s $ time ruby --ng knapsack/knapsack_rec.rb real 0m5.213s user 0m0.022s sys 0m0.021s
Первый запуск немного медленный, поскольку JVM запускается, но после этого мы получаем незначительное улучшение. Я думал, что время запуска JVM будет большей частью времени работы, но я думаю, что нет!
Я думал, что попробую это и на Python, потому что по одной из предыдущих проблем Исаия смог написать гораздо более быстрые версии на Python, поэтому я хотел посмотреть, будет ли это так и здесь.
Это было решение Python :
def knapsack_cached(rows, knapsack_size, index):
global cache
if(index is 0 or knapsack_size is 0):
return 0
else:
value, weight = rows[index]
if(weight > knapsack_size and knapsack_size not in cache[index-1]):
cache[index-1][knapsack_size] = knapsack_cached(rows, knapsack_size, index-1)
else:
if(knapsack_size not in cache[index-1]):
option_1 = knapsack_cached(rows, knapsack_size, index-1)
option_2 = value + knapsack_cached(rows, knapsack_size - weight, index-1)
cache[index-1][knapsack_size] = max(option_1, option_2)
return cache[index-1][knapsack_size]
knapsack_size, number_of_items, rows = # worked out from the file
result = knapsack_cached(rows, knapsack_size, number_of_items-1)
print(result)
Код в значительной степени совпадает с версией Ruby, но интересно, что он работает быстрее:
$ time python knapsack/knapsack.py real 0m4.568s user 0m4.480s sys 0m0.078s
Я понятия не имею, почему это было бы так, но это было для всех алгоритмов, которые мы написали до сих пор. Если у кого-то есть какие-либо идеи, я заинтригован, чтобы услышать их!