ИСТИНА

Задача о Рюкзаке является частным случаем многокритериальной комбинаторной оптимизации. Это NP-полная проблема в ее общем виде. Кроме того, в многокритериальном случае сообщается о многих реальных приложениях, связанных с составлением бюджета капитальных вложений, планированием восстановления загрязненных участков световых станций, проблемами перемещения, возникающими в биологии сохранения. В течение нескольких десятилетий в литературе исследовалось несколько эвристических и точных подходов к определению эффективного набора или уменьшенного эффективного набора для многокритериальной задачи рюкзака. Поскольку компьютеры имеют очевидные ограничения в хранении, скорости и интеллекте, появились методы вычисления ДНК, особенно для их эффективного параллелизма. В последнее время многие исследователи продемонстрировали, что вычисления с помощью самосборки ДНК-плиток могут быть масштабируемыми, и это рассматривается как перспективный метод в нанотехнологиях.