|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rick Hustle 2:5030/961.111 07 Oct 2001 00:13:35
To : Igor Krassikov
Subject : Распределение файлов по CD
--------------------------------------------------------------------------------
Отвечаю на ваше письмо от 04.10.2001, тогда писал(а) Igor Krassikov
к Rick Hustle, а было тогда на часах 21:41:00.
RH>> Есть N файлов, (разных размеров < ёмкости CD болванки) и k CD болванок
IK> [...skipped...]
RH>> Интересем алгоритм решения этой задачки отличный от "тупого" перебора
RH>> комбинаций. Т.к. уже при кол-ве файлов полядка > 12 задача становится
RH>> ОЧЕHЬ долгорешаемой.
IK> Припоминается, что лет 7-8 назад при обсуждении алгоритма для
IK> размещения файлов по дискетам утверждалось, что сия задача NP-полная.
Поясни, пожалуйста, что такое "NP-полная задача"?
IK> Впрочем, какие-то эвристики приводились - типа размещения в каждой
IK> ситуации наибольшего возможного файла, что ли...
По-подробней, пожалуста...
Rick.
---
* Origin: Tы чавой-то сам не свой? Hерумяный, неживой? (2:5030/961.111)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
