|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stepan M. Pechkin 2:5030/1688.11 06 Feb 2003 22:21:00
To : Aleksey Zelenin
Subject : Задача о pанце.
--------------------------------------------------------------------------------
Wednesday February 05 2003 15:33, Aleksey Zelenin wrote to Lorinets Roman:
AZ> Вот эту. Где бы пpо нее найти что-нибудь готовенькое в нескольких
AZ> ваpиантах и желательно на C/C++.
Вариантов, собственно, два. Перебор (Omega(2^n)) и динамический алгоритм.
Первый тривиален, второй есть в Кормене, как минимум. Я так думаю, что,
поскольку константа динамического алгоритма весьма здорова (O(n*W), если не
ошибаюсь; n - кол-во предметов, W - вместимость рюкзака), следует каждый раз
прикидывать, какой из вариантов окажется выгоднее.
Да! W должно быть целочисленным, и все конкретные весы предметов тоже.
Stepan (-: с приветом :-)
tmpechkin@hotmail.com http://pechkin.rinet.ru
ICQ#21296772
---
* Origin: >*< Пистолет, партбилет, "Минулет"... (FidoNet 2:5030/1688.11)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
