Есть у кого нибуть исходник на С задачи о рюкзаке (Knapsack problems - subset sum) без применения рекурсии ?
Условие и ограничения следующие:
X=(1,2,3,...,N), A принадлежит множеству {0, 1};
sum(X[i]*a[i])=s;
Найти подпоследовательности размерности K (K<=N), сумма которых была бы равной S.
Буду очень благодарен.

А почему без рекурсии, она прямо так и просится сюда, особенно, когда S > N

Посмотри алгоритм Беллмана. Это типичная задача на динамическое программирование.
Без рекурсии, сложность N*W

Это сообщение отредактировал(а) Alex101 - 31.1.2003, 01:20

Цитата

А почему без рекурсии, она прямо так и просится сюда, особенно, когда S > N

Вариант с рекурсией после N=50 очень сильно увеличивает время выполнения. Вот и хотелось бы уменьшить время вычисления бы счет исключения обработки вызова рекурсивных процедур.

Воспользуйся методом частичного (неявного) перебора. Прекрасно описан в книге: Вагнер Г. Основы исследования операций. Том 2. - М.: Мир, 1973.
Там как раз твой случай.
Если не сможешь найти эту книгу (весьма редкая!), то похожую задачу найдешь в журнале "Радиотехника" № 10 за 1997 г. Статья "Решение задачи управления временнЫми ресурсами спутниковой системы связи".

Вот, нашел. И там в конце статьи есть избавление от рекурсии.

Решение задачи о рюкзаке.

Алгоритм решает задачу о рюкзаке, которая формулируется так: Дан, упорядоченный по неубыванию, массив A целых положительных чисел и некоторое Sum, необходимо найти все подпоследовательности массива A сумма элементов которых равна в точности Sum. Подробно решение рассматривается в статье Перебор и его сокращение.
http://doors.infor.ru/allsrs/alg/paper/perebor.html
В результате работы алгоритма получаем переменную L равную количеству найденых последовательностей. Сами последовательности помещаются в масcив строк Results, каждая строка представляет номера элементов массива A, разделенные запятыми.

Цитата

Вот, нашел. И там в конце статьи есть избавление от рекурсии.

Кто ищет, тот всегда найдет!
Это дает повод еще раз напомнить:

http://forum.vingrad.ru/index.php?act=ST&f=13&t=4397

В какой литературе или на каких сайтах можно найти алгоритм или програму для решения задачи про рюкзак?

Цитата

В какой литературе или на каких сайтах можно найти алгоритм или програму для решения задачи про рюкзак?

См. ссылку выше.

Нужна реализация Алгоритма Беллмана-Форда. Кто может помогите. Адрес [email protected]
Добавлено @ 23:05
Т.е. нужна визуализация

Вот тут куча алгоритмов

Люди добрые,помогите,пожалуйста!Мне позарез нужно решение задачи о рюкзаке на паскале с таким условием:"Дано М различных предметов. Известны вес и стоимость каждого. Определить,какие предметы надо положить в рюкзак,чтобы общий вес не превышал 30кг.,а общ. стоимость была максимальной."
Кто располагает временем и информацией , слёзно прошу написать на [email protected]