Точнее, не совсем про рюкзак. Разница в том, что вес должен быть не <= нужного, а == нужному.

А что за задача-то? Я просто не в курсе, никогда не слышал о такой.

Вкратце:

Есть n предметов, каждый имеет вес w и стоимость p. Нужно выбрать предметы так, чтобы получить макс. стоимость, не превысив лимит по весу. В моем случае особенность: нужно, чтобы сумм. вес был равен ограничению.

Вес, как я понимаю, рандомный и стоимость прямо пропорциональна весу?

гусар очевидность смеет сообщить

Время исполнения зависит от имплементации и от набора входных данных.

lor_mokey> Задача про рюкзак, 4000 предметов, суммарный вес до десяти миллионов. Возможно ли вложится в 5 секунд?

Легко

Стоимость какая угодно.

Каким образом?

Нужны все решения?

Распараллелить на бесконечно большое кол-во компьютеров.

З.Ы. Какое условие такие и ответы.

Ограничения на входные данные я упомянул в условии. Нужно, чтобы проходило любой тест, подходщий под эти ограничения.

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

Распараллелить на бесконечно большое кол-во компьютеров.

Хватило бы и на несколько десятков. А нужно без распараллеливания, в один поток.

Нужно решение, дающее макс. стоимость. Или же инфа, что такого решения нет.

Ограничения на входные данные я упомянул в условии.

Ограничения на входные данные я упомянул в условии. Нужно, чтобы проходило любой тест, подходщий под эти ограничения.

Нда, смотрю на связи очередное молодое дарование.

Я считаю, что возможно. Начинай меня опровергать

Как уже сказали - смотря какой мощности кластер)

А откуда она берется? Не самому же вводить :D

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

И в чём у тебя проблема? На эти темы были изведенны тонны бумаги.

Только в медлительности самого обычного ДП-решения (сложность N * M, где N - вес, M - количество предметов).

Озвучь степень «медлительности»

побуду капитаном:

4000 * 10 000 000 = 40 000 000 000 итераций на макс. входных данных.

Итого меньше минуты, что очень близко к требуемым нескольким секундам.

Смотрю, на связи очередное (малолетнее-)быдло с раздутым ЧСВ, которому лишь бы ляпнуть.

Биективная мероморфная экстраполяция.

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

Ознакомься

Новое поколение задротов РПГ решает оптимизационные задачи!

4000 * 10 000 000

откуда 10 000 000 в оценке?

можно, разрешаю.

Нет таких рюкзаков, батенька... если тока предметы не бриллианты а вес не в каратах меряете. Что, линять собрались?;-)

Вы понимаете, что решение не единственное?

man knapsack packing

Логистическая. Оптимальное использование объема.

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

Ты упоролся?

Lol, ну а не же NP-complete. Так что давай иди статьи читай, смотри какие подходы тебе подходят. Либо строишь выпуклую оболочку задачи и решаешь ее, либо используешь глобальную оптимизацию и всякие MCMC. У всех разные гарантии на сходимость и оценки снизу, у всех разное время работы.

Lol, ну а не же NP-complete. Так что давай иди статьи читай, смотри какие подходы тебе подходят. Либо строишь выпуклую оболочку задачи и решаешь ее, либо используешь глобальную оптимизацию и всякие MCMC. У всех разные гарантии на сходимость и оценки снизу, у всех разное время работы.

Она псевдополиномиальна, успокойся. Решается за время 4000*10^6

ok, stay with that

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

Что-что-что??

Дискретная задача о рюкзаке относится к классу NP-полных.

Как вещественные числа делают «всё хорошо» и почему целые всё портят?

Только добил эту лабу по ИИ. Но у меня там был simulated annealing, что его изрядно замедляет

Правильно... Берем ЛЮБОЙ компьютер из TOP-500 он решит и за меньшее время.

man целочисленное программирование

Продолжай

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

И как всё связать с задачей из сабжа?

А то что задача о рюкзаке есть задача целочисленной оптимизации.

И каким боком рассуждения о задачах, «определённых над полями вещественных чисел» относятся к обсуждаемой задачи?

И что такое «определенная над полем вещественных чисел» задача?

Область допустимых значений для варьируемых переменных влияет на вычислительную сложность задачи. В данном случае кол-во предметов положенных в рюкзак - натуральные числа и задача как уже сказано NP-полная. Т.е. быстрых методов решения не существует.

Сразу видно, слушал курс «Теория сложности алгоритмов». На какой специальности/факультете учился/учишься?