Добрый день, Дорогие форумчане..
Может кто видит, как можно сделать более оптимально:
У нас есть рюкзак, его общий объем, вещи и их вес.
Т.е. предположим, что у нас есть 5 вещей.
Я их представляю как массив из 5 элементов, в котором 1, значит берем вещь, 0 - значит не берем.
Необходимо перебрать все варианты и найти такой, в котором мы бы взяли в рюкзак вещи, которые в сумме дают максимальный вес, т.е.
11111
01111
00111
00011
00001
10111
10011
и в таком духе...

В общем необходим как раз такой перебор реализовать. А к рюкзаку уже сам прикручу.
Я это делал с помощью рекурсии и все хорошо получается, но т.к. сейчас задание на CUDA, а она пока что не поддерживает рекурсию (у меня компиль ругается, хотя в 4 вроде как сказано, что уже поддерживает).

Из своих соображений:
Перегонять двоичное число разбивая его по символьно в массив.
Еще как вариант:

но думаю данный код уж точно не оптимальный(((

И если есть ребята, которые с технологией CUDA работали, может подскажите, как лучше параллелить данную задачу. Я пока что делал так:
Если 2 потока, то начинаем со второй вещи, а автоматом для первого потока кладем эту вещь в рюкзак.
если 4 потока, то так же делаем, но с 2мя вещами.
Как заметно, минус данной логики - то, что количество потоков должно быть кратно 2ке, иначе будет неправильно распределяться.


В общем буду благодарен, если поможете советом или алгоритмом))


Это сообщение отредактировал(а) AGENTxXx - 10.6.2012, 20:50

Это сообщение отредактировал(а) 586 - 10.6.2012, 20:37

586, можете код пояснить ваш, а то я что т не догоняю.....

Четвертый том Кнута вам в помощь, или если на русском - то превыпуск 2 четвертого тома. В Интернете точно имеется 

Мое мнение - поскольку вам веса считать - лучше кодом Грея (по сути, добавляется или убирается один предмет, так что вес легко считать - в одно действие, много суммировать не надо - так что будет работать быстрее всего.

Погуглил.. Тоже видел в одном месте с помощью "кода Грея" считали.
Хорошо, посмотрю тогда в этом направлении тоже.
Но опять же вопрос: если применять код Грея, распараллелить там можно?
Нет ли зависимости от предыдущего действия?

Мне параллелить нужно, без этого не прокатит.. Сейчас так сказать первый вариант уже со своим алг. сварганил, но он у меня пока что очевидно не выглядит параллелевидным.. так что нужно думать еще....

Честно говоря, не помню я, насколько там генерация зависит только от предыдущего состояния, но думаю, что можно.

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


Это сообщение отредактировал(а) disputant - 11.6.2012, 17:47

1) Получать все возможные комбинации из наборов предметов очень просто - двоичная запись чисел от 0 до 2^N-1 (т.е. для 5 - 00000, 00001, 00010, 00011, ..., 11110, 11111);
2) генерировать их также элементарно - запускаете все потоки одной пачкой;
3) вычислять, брать i-й вес или нет - определением, есть ли i-й бит.

псевдокод (с cuda не работал, но идея такая):


Это сообщение отредактировал(а) Silent - 13.6.2012, 12:51