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

Так тема и зависла...
У меня вот возникла подобная проблема.
Т.е. тоже задача о рюкзаке, но с немного модифицированым условием.
Таким как тут:
Процедура поиска
(к сожалению топик кажется тоже засох )
В Инете я среди общего мусора нашел вот такой алгоритм:
http://www.mgopu.ru/PVU/2.1/Recurs/BacketT...rn/task_ruc.htm
но к сожаления я так и не понял ничего из ихней схемы.
Может к-нить помочь?

Или вот что я думал:
если судя по той инфо, которую я накопал в Инете такая задача решается только методом полного перебора, то возникли такие наброски алогритма:
1. Высчитываем количество комбинаций С по формуле Бернулли (не перестановок! гже просто факториал) группы K элементов из множества N.
2. Формируем массив размерностью полученого числа С.
3. Поочереди в цикле i=1:C вызываем хитрую ф-цию (см. ниже), парсим ее результат, получаем комбинацию и высчитываем для каждой полученной комбинации её коеф. оптимальности и заносим в масив из п.2.
4. Находим в массиве максимальное значение. Порядковый номер ячейки масивва и будет искомая комбинация. (опять вызываем хитрую ф-цию - которая по-сути вернет уже готовый результат)

Вся проблема в п.3, а именно: нужна вот та самая хитрая ф-ция на вход которой подается 3 параметра: K, N, I которая бы возвращала вектор (ну хотя-бы в виде стринга, со значениями разделенными запятой) порядковых номеров элементов из множества N соотв. I-той комбинации.

Например:
N = 4
K = 2

Вообще все комбинации (4!/(2!*2!) = 6 штук):
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

так вот:
f(4, 2, 2) - возвращает "1, 3"
f(4, 2, 5) - возвращает "2, 4"

Помогите, пожалуйста, с реализацией. Уже просто ничего в конце дня не соображаю... Хотя, до завтра может чо-нить сам докумекаю, но все равно хотелось бы услышать отклики на тот вариант в ссылке, где я вообще ничего не понял, и тот вариант реализации который я предложил. Спасибо.

Нет, ребята... Я тут вечерком подумал - лажа какая-то полная.
О каком полном переборе может ити речь?
Если, например, мне надо выбрать со склада 15 товаров, на котором их 25 видов по критерию: минимальная общая стоимость + общий вес не более 60 кг.
Количество комбинаций: 25!/15!/10! = 3268760 комбинаций!!!
Это ж сколько у меня мегабайт оперативки только масив критериев займет?! А?
А время?!!
Даже если учесть, что комп будет высчитывать 100 комбинаций в сек. (что маловероятно) то всеравно уйдет около 9-ти(!) часов времени! И это только для одногопокупателя, а их может быть десяток...

Хотелось бы услышать мнение Esperanto о даной проблеме. Может есть какй-то метод монте-карло (или как там его) который бы высчитывал искомую комбинацию хотя-бы на порядок быстрее, пусть даже с точностью где-то до 80%? Т.е. что-бы возвращаемый результат удовлетворял изначальному критерию по массе (что-бы человек смог унести товар) но вот по миним. стоимости уже пусть немножко привирает иногда - терпимо.

Есть целая группа методов - генетические алгоритмы, позволяют находить КВАЗИОПТИМАЛЬНЫЕ решения. Незаменимы именно для таких случаев, когда решение не обязательно должно быть самым лучшим, а вполне достаточно просто хорошего решения.

Инфу можно найти в инете - я бы и сам тебе поискал, но превысил квоту по зарубежному траффику.

Если будут вопросы по генетическим алгоритмам - задавай.

Насчет ГА, например фак и сорцы либы на http://sourceforge.net/projects/cpplibga/

Может посмотри здесь "задача о рюкзаке"

ну если автору хватит ОДНОЙ комбинации, там динпрог просто рулит, сложность О(N*N) а по последней ссылке требовалось найти ВСЕ, а значит полным (или неполным) перебором наши программы можно использовать, воткнув exit при нахождении первой комбинации.

Вот накатал на васике. (рюказчки).

Рюкзачок (Файл 3.17 Кб.)

Цитата Dr._S, 4.10.04, 07:46

Вот накатал на васике. (рюказчки).

Да нет. Совсем не то.
Тут, я так понял, просто задается макс. вес (напр. 100 кг.) и потом ищется комбинация вещей, которая бы не переваливала за опред. макс. критерий. (напр. 25 кг.)
Тут налицо простая однопараметрическая оптимизацмия.

Нужна же двухпараметрическая: не превышает макс. допустим. вес при этом миним. суммарная стоимось.

Chow,

Цитата

Тут, я так понял, просто задается макс. вес (напр. 100 кг.) и потом ищется комбинация вещей, которая бы не переваливала за опред. макс. критерий. (напр. 25 кг.)

, не то чтобы перевалила, а комбинация равная эту весу, ни больше, ни меньше. Не пойму какие проблемы, тебе находит комбинации, теперь сам проанализируй их на наименьшую стоимость. Заведи массив в котором индексом цены будет вес предмета и все, какие проблемы? Получи сумму всех комбинаций, сравни и вуаля.

Цитата Dr._S, 4.10.04, 12:59

, не то чтобы перевалила, а комбинация равная эту весу, ни больше, ни меньше. Не пойму какие проблемы, тебе находит комбинации, теперь сам проанализируй их на наименьшую стоимость.

ОК. попробую. спасибо. (хотя, мне надо именно что-бы не перевалила, а не больше-меньше)
Мне кажется, что это и есть полный перебор. Так что тут траблы с быстродействием будут. Хотя... Попробую. Тот вариант что вы прислали вроде-бы шустренько работает.

Chow,

Цитата

хотя, мне надо именно что-бы не перевалила, а не больше-меньше

, ну так и есть, я же написал

Цитата

...комбинация равная этому весу, ни больше, ни меньше...

Опять вы меня не поняли.
В вашем варианте производится поиск любых наборов элементов, суммарная масса которых точно соответств. заданой.
Мне же нужно: найти наборы состоящие точно из N элементов, суммарная масса которых не превышала бы (т.е. была бы <=) заданую.

Таких комбинаций будет ОЧЕНЬ много. И вот потом, мне надо будет из них выбрать одну - ту у которой суммарная стоимость (еще один дополнительный параметр наряду с массой) меньше всех!

Chow,

Цитата

Мне же нужно: найти наборы состоящие точно из N элементов, суммарная масса которых не превышала бы (т.е. была бы <=) заданую

, ну хорошо, сделай проверку (в поиске вариантов), если набран нужный вес и кол-во элементов = твоему N, то выводишь этот набор или записываешь, иначе - игнарируешь. И всё.

Цитата Dr._S, 6.10.04, 05:26

ну хорошо, сделай проверку (в поиске вариантов), если набран нужный вес и кол-во элементов = твоему N, то выводишь этот набор или записываешь, иначе - игнарируешь. И всё.

Да не набран нужный вес!!!
Мне не обязательно его точно набрать! Надо что-бы он был меньше заданого допустимого.

Добавлено Сегодня, 08:55
Бли-и-ин...
Ну сколько еще можно объяснять.
Делаю последнюю попытку и расжевываю все до последнего.
Допустим есть аэроклуб любителей-парашютистов. В нем состоит 100 чел.
И вот пришла в клуб заявка на международные юношеские соревнования по групповым прыжкам.
Правила проведения:
1. групповой прыжок проводится в составе 15 чел. (больше на борт просто самолет не может взять - всего 15 посадочных мест)
2. суммарный вес группы парашютистов не должен превышать 1130 кг. (иначе самолет не взлетит)
3. чем меньше сумарный (или средний) возраст группы - тем больше очков она получит за прыжок. (т.е. мастерство тоже учитывается, но даются колоссальные льготы на то, что прыгают юные участники, а не махровые мастера).

Теперь допустим все 100 членов клуба практически имеют одинаковый уровень мастерства.
И перед руководством стоит задача: выбрать из 100 клубней 15 таких человек, что-бы их общий вес не превышал 1130 кг., и при этом сумарный (или средний) возраст был как можно меньше!

(Тут я наплел немного про возраст - для ясности и простоты. На самом деле никаких льгот за возраст не дается, каждый участник клуба имеет другой показатель - уровень своего мастерства и руководству клуба надо выбрать 15 чел. - самых мастеровитых и что-бы не очень толстых...)

Chow, на кой х№" ты мне это объясняешь. Все и так понятно.

Цитата

Да не набран нужный вес!!!
Мне не обязательно его точно набрать! Надо что-бы он был меньше заданого допустимого.

, тогда еще проще, условие: кол-во_парашютистов = ограничение_по_кол-ву AND вес_отбираемых_парашютистов <= допустимый_вес

кол-во_парашютистов - кол-во при переборе из всей команды
ограничение_по_кол-ву - установленное кол-во человек в команде для соревнований
вес_отбираемых_парашютистов - вес отбираемых парашютистов при переборе
допустимый_вес - допустимый вес для самолета