Xpoint
   [напомнить пароль]

Задача о рюкзаке

Метки: [без меток]
2006-01-07 16:58:16 [обр] Mikae[досье]

Всем привет!

Реализую задачу рюкзака (язык С), для варианта 0/1. Требование — наличие рекурсии. Как я понимаю, нужен полный перебор всех вариантов. Перебор представляю себе примерно так (для 5и вещей):

1, 2, 3, 4, 5.

1-2, 1-3, 1-4, 1-5.
2-3, 2-4, 2-5.
3-4, 3-5.
4-5.

1-2-3, 1-2-4, 1-2-5.
1-3-4, 1-3-5.
1-4-5.

2-3-4, 2-3-5.

3-4-5.

1-2-3-4, 1-2-3-5.

1-2-4-5.

1-3-4-5.

2-3-4-5.

1-2-3-4-5.

Вроде все логично, все варинаты перебираются. Но у меня не получается уложить это в рекурсивный алгоритм... Каким боком тут должна присутствоваь рекурсия?.. Или я не правильно подошел к вопросу о переборе?..

Need help, в общем...
Заранее благодарен :).

спустя 1 час 30 минут [обр] Pil(0/22)[досье]
Mikae[досье]А Вы можете для не просвященных саму задачку написать. А то лично мне формулировка "Реализую задачу рюкзака (язык С), для варианта 0/1" ни о чем не говорит.
спустя 1 час 19 минут [обр] Mikae[досье]

Пардон, фрмулировка:

Есть N вещей, каждая вещь имеет вес и стоимость. Есть рюкзак, вместимостью W kg. Необходимо найти такую комбинацию вещей, чтобы их суммарный вес не превосходил W и стоимость была максимальной. 0/1 значит, что каждая вещь дана в единственном экземпляре (т.е. надо решить, брать/не брать).

Трудность — не знаю как организовать полный перебор рекурсивно...

спустя 22 часа [обр] Владимир Палант(27/4445)[досье]
У каждой вещи есть порядковый номер (1..n). В первый раз функция вызывается с порядковым номером 1, стоимостью и весом 0 — func(1, 0, 0). При вызове func(i, k, w) функция вызывает себя рекурсивно дважды — один раз как func(i+1, k, w) (вариант "вещь i не брать") и как func(i+1, k+k_i, w+w_i). Второй вызов не происходит, если w+w_i больше W. Функция сравнивает возвратные значения двух вызовов и возвращает большее. Условие для окончания рекурсии: если i > n, то ничего этого функция не делает, а просто возвращает k.
спустя 1 час 47 минут [обр] Mikae[досье]

Спасибо!

Это именно то, что мне нужно :)

Powered by POEM™ Engine Copyright © 2002-2005