задача о рюкзаке 0-1

[was3110]

Добавляю на другой день...
спасибо MihalNik, что донес до меня несерьезность ограничений.
Да, это еще детский "велосипед".
Тем не менее это программа-калькулятор для задачи о рюкзаке 0-1.
Да, я не готов платить за тестирование.
Тестирование могу провести и сам... Знать бы до каких пределов...
Но готов любому желающему предоставить этот калькулятор, как инструмент для быстрого решения задачи о рюкзаке (ограничения в 12000 предметов и 20 млрд веса не вечны, буду развиваться). контакты в профиле. Буду благодарен за бесплатное тестирование.

[was3110]

Как-то не приятно прозвучали слова о мошенничестве...
Хоть так покажу, что программа работает... А точность работы проверит тот, кому интересно.

[Alex11223]

Random() тоже работает... А точность работы проверит тот, кому интересно.

Сообщение от was3110

Да, я не готов платить за тестирование.

Тогда причем тут Фриланс?

[was3110]

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

[Аватар]

Алгоритма нет. Есть exe

[was3110]

Так точно! Алгоритма нет. Такого алгоритма нет в Википедии. Но ехе все равно работает. Вот только сравнить мне его не с чем... В интернете аналогов не нашел... с такими параметрами.

[MihalNik]

Сообщение от was3110

сравнить мне его не с чем... В интернете аналогов не нашел... с такими параметрами.

С какими параметрами? Где они указаны? Где диапазон кол-в и значений?

Такого алгоритма нет в Википедии

Нобелевская премия сразу

[was3110]

С Вами, MihalNik, поделюсь первым...
Ищу программу для решения задачи о рюкзаке 0-1, допускающую набор предметов от 1000 и выше (свою тестирую сейчас на 25 тысячах) и объем свыше 10 млрд. (на моей сейчас ограничивающая константа 50 млрд)
Вес предметов на моей double >0... ищу аналог с любым.
Стоимость предмета на моей currency >0 ... ищу аналог с любой

[MihalNik]

Сообщение от was3110

double

Соответственно потери будут при выходе за длину мантиссы. N*M должно укладываться в точность формата данных.

В интернете надо искать различные соревнования для подобных алгоритмов, но требования форматов могут оказаться неподходящими. Либо можно создать конкурс самому, например, здесь проводились какие-то соревнования ботов к игре. Создание тестов не представляет трудности, какие-нибудь консольные приложения. Можно назначить приз для привлечения интереса. Опять же, либо необходимо доверие для отправки программ проводящему конкурс, либо участники должны посылать друг другу задания и результаты (но тогда время ставится под сомнение, у всех разное железо, испытать можно разве что на предельные возможности и сам факт решения).

В жизни задачи укладки обычно многокритериальные, чаще геометрические.
Простейший 32-разрядный рюкзак пишется в несколько строчек кода, хотя его может и не быть в википедии Увеличение ёмкости на 1-2 цифры к 10 немного чего даёт (можно не заморачиваться с оптимизацией, а взять побольше оперативы - она ведь пригодится и для других целей), интерес к значениям в десятках млрд. слишком специфичен (у double еще нужно проверять чтобы значения всех данных лежали в пределах возможности одной мантиссы), теоретический лежит в намного больших порядках.

[was3110]

Спасибо, MihalNik! Все толково. Все разложено по полочкам. Жму на весы...