Добрый день,
Алгоритмы ранцев не "щелкают" в моей голове. Я хорошо знаю, как ответить на вопрос о проблемах с рюкзаком разных вариаций (рюкзак 0-1, рюкзак с пряностями и т. Д.), Но я не совсем понимаю сам алгоритм;и я хотел бы заполнить пробел
Чтобы сделать мой вопрос менее расплывчатым, я разбил свой вопрос на несколько подвопросов. Также Вот мой типичный ответ на вопрос о ранце на экзамене:
Построить X-мерную матрицу (где X - это число переменных, за которыми нужно следить). Из точки 0 {0,0, ... 0} вычислите соседние узлы, а затем по полученным результатам перейдите к следующей диагональной точке в матрице с результатом, дающим, безусловно, наиболее оптимальное решение. Повторяйте до тех пор, пока все рассмотренные варианты в алгоритме не будут исчерпаны
Как мы узнаем, что алгоритм рюкзака работает (кроме эмпирических наблюдений)? В частности, как мы можем точно знать, что не существует необязательной конфигурации, если она дает более оптимальный результат, чем наш алгоритм возвращает в конце?
Использование "X-мерной"матрица "кажется очень избыточной в плане использования памяти, есть ли более оптимальная структура данных для задачи о ранце? Возможно, бинарное дерево min-max (что «кажется» более оптимальным для этого случая)
Предположим, у нас очень большой рюкзак. Разве не было бы эффективнее заполнить рюкзак жадным подходом (с предметом, дающим наилучшее соотношение), пока не останется очень мало места? На мой взгляд, пока здесь не осталось 2*(largest item) места?
Приветствия