https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0_fixed_partinioning 2026-05-03T11:57:06Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%AD%D0%B2%D1%80%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0_fixed_partinioning&diff=6504&oldid=prev 2017-12-09T14:59:52Z

<p>Новая страница: «&#039;&#039;Эвристика fixed partinioning&#039;&#039; — техника, позволяющая сокращать перебор и получать приближенны…»</p> <p><b>Новая страница</b></p><div>''Эвристика fixed partinioning'' — техника, позволяющая сокращать перебор и получать приближенные полиномиальные алгоримтмы из алгоритмов динамического программирования, ищущих точное решение.<br /> Это обобщение процедуры скейлинга коэффициентов входной задачи, рассмотренной в разделе про FPTAS-алгоритм для рюкзака.<br /> <br /> Например, для того же рюкзака, мы не трогали бы коэффициент, но разделили весь диапазон возможных значений &lt;m&gt;[0, \ldots, \sum_{i=1}^n c_i]&lt;/m&gt; на P эквивалентных интервалов, и в алгоритме динамического программирования, отбирали бы самый легкий набор для того «интервала - класса эквивалентности по стоимости», куда бы он попал.</div>

StasFomin