Просто для удовольствия я попробовал точное решение для динамического программирования.Написано на Python, из-за моей абсолютной уверенности, что вам не следует оптимизировать, пока вы не должны это делать; -)
Это может обеспечить либо начало, либо грубое представление о том, как близко вы можете приблизиться, прежде чем прибегать к приближению.
Код основан на http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem,, следовательно, наименее информативные имена переменных m, W, w, v.
#!/usr/bin/python
import sys
solcount = 0
class Solution(object):
def __init__(self, items):
object.__init__(self)
#self.items = items
self.value = sum(items)
global solcount
solcount += 1
def __str__(self):
#return str(self.items) + ' = ' + str(self.value)
return ' = ' + str(self.value)
m = {}
def compute(v, w):
coord = (len(v),w)
if coord in m:
return m[coord]
if len(v) == 0 or w == 0:
m[coord] = Solution([])
return m[coord]
newvalue = v[0]
newarray = v[1:]
notused = compute(newarray, w)
if newvalue > w:
m[coord] = notused
return notused
# used = Solution(compute(newarray, w - newvalue).items + [newvalue])
used = Solution([compute(newarray, w - newvalue).value] + [newvalue])
best = notused if notused.value >= used.value else used
m[coord] = best
return best
def main():
v = [int(l) for l in open('filesizes.txt')]
W = int(sys.argv[1])
print len(v), "items, limit is", W
print compute(v, W)
print solcount, "solutions computed"
if __name__ == '__main__':
main()
Для простоты я просто рассматриваю размеры файлов: когда у вас есть список размеров, которые вы хотите использовать, вы можете найти некоторые имена файлов с этими размерами, просматривая список, так что нет смысла запутывать имена файлов в ядре, медленночасть программы.Я также выражаю все в кратных размерах блока.
Как вы можете видеть, я закомментировал код, который дает реальное решение (в отличие от значения решения).Это было для экономии памяти - правильный способ хранения списка используемых файлов - это не один список в каждом решении, а чтобы каждое решение указывало обратно на решение, из которого оно было получено.Затем вы можете рассчитать список размеров файлов в конце, пройдя по цепочке, и вывести разницу между значениями на каждом шаге.
Со списком из 100 случайно сгенерированных размеров файлов в диапазоне 2000-6000(Я предполагаю, что блоки 2 КБ, то есть файлы размером 4-12 МБ), это решает проблему W = 40 КБ за 100 секунд на моем ноутбуке.При этом он вычисляет 2,6 млн. Возможных решений на 4 млн.
Сложность равна O (W * n), где n - количество файлов.Это не противоречит тому факту, что задача является NP-полной.Поэтому я, по крайней мере, подхожу к решению, и это только в неоптимизированном Python.
Очевидно, что теперь требуется некоторая оптимизация, потому что на самом деле ее нужно решить для W = 4M (DVD на 8 ГБ) и скольких файлов выесть (скажем, несколько тысяч).Предполагая, что программе разрешено занимать 15 минут (сравнимо с временем, необходимым для записи DVD), это означает, что производительность в настоящее время невелика примерно в 10 ^ 3 раз.Таким образом, у нас есть проблема, которую довольно сложно быстро и точно решить на ПК, но не за пределами технологии.
Использование памяти является основной проблемой, так как, как только мы начнем использовать swap, мы замедлим,и если у нас заканчивается виртуальное адресное пространство, у нас большие проблемы, потому что мы должны реализовать собственное хранилище решений на диске.Мой тестовый запуск достигает пика в 600 МБ.Если вы написали код на C на 32-битной машине, каждое «решение» имеет фиксированный размер 8 байтов.Таким образом, вы можете сгенерировать массивный двумерный массив из них без выделения памяти в цикле, но в 2 ГБ ОЗУ вы можете обрабатывать только W = 4M и n = 67.К сожалению, DVD вышли.Это может почти решить проблему для компакт-дисков размером 2 k, хотя: W = 350k дает n = 766.
Редактировать: предложение MAK вычислять итеративно снизу вверх, а не рекурсивно сверху вниз, должно значительно уменьшитьтребование к памяти.Сначала вычислите m (1, w) для всех 0 <= w <= W. Из этого массива вы можете вычислить m (2, w) для всех 0 <= w <= W. Затем вы можете выбросить все m (1, w) значения: они вам не понадобятся для вычисления m (3, w) и т. Д. </p>
Кстати, я подозреваю, что на самом деле проблема, которую вы хотите решить, может быть упаковка бинапроблема , а не просто вопрос о том, как добиться максимально возможного заполнения DVD.Вот если у вас есть куча файлов, вы хотите записать их все на DVD, используя как можно меньше DVD.Существуют ситуации, когда решить проблему упаковки бункера очень просто, но решить эту проблему сложно.Например, предположим, что у вас есть 8 ГБ дисков и 15 ГБ небольших файлов.Потребуется некоторый поиск, чтобы найти максимально возможное совпадение с 8 ГБ, но проблема упаковки бина будет решена тривиально, если поместить примерно половину файлов на каждый диск - не имеет значения, как именно вы их разделите, потому что выбудешь тратить 1 ГБ места, что бы ты ни делал.
Все это говорит о том, что есть чрезвычайно быстрая эвристика, которая дает достойные результаты большую часть времени. Проще всего просмотреть список файлов (возможно, в порядке убывания размера) и включить каждый файл, если он подходит, исключить его в противном случае. Вам нужно только вернуться к чему-то медленному, если быстрые приближенные решения не «достаточно хороши», для вашего выбора «достаточно».