https://sun9-65.userapi.com/impg/OnSOoGKccieAZjJgx-F3hxP2OXKFPGTvTCpACg/Bj_sOhLQcYY.jpg?size=1920x1080&quality=96&sign=5cda9db9d8339cc765f415093aa410c5&type=album

В общем, я нашёл один алгоритм, который очень близок к 100% успешных результатов. По нему видно, что он практически идеален и прост для решения данной задачи.

Первые числа в таблице идут по возрастанию, потому что они являются ограничениями для данной задачи. Я решил посмотреть что будет если менять ограничение внутри одной задачи. Как оказалось, алгоритм хорошо себя чувствует, кроме случаев с ограничениями 38 и 46.

В первом случае, по алгоритму должно было быть 9+1 с "долларами" 4 и 1 соответственно. Однако это будет ошибкой, если посмотреть на результаты. 1+5+2+8+10=26, 38-26=12, 9+1=10 не покроют эту разницу, однако сумма их "долларов" составит 5, в то время как существует аналог данному выбору, 8+4 с "долларами" 3 и 2 соответственно, что решит эту проблему.

Во-втором случае аналогично: 8+1 с" долларами" 3 и 1 соответственно, аналог:7+4 с "долларами" 2 и 2 соответственно. 46-35=11, 8+1=9, 7+4=11, как и в первом случае, разницу покроет аналог, а не вариант алгоритма.

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

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

задан 23 Май '21 16:42

может таки сформулируете условие... то, что написано, никак не коррелирует с моим представлением о "задаче о рюкзаке"...

(23 Май '21 17:48) all_exist

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

К сожалению, я любитель и не знаю как заведено писать.

(23 Май '21 18:13) DarKProGameR

доллары - это цена?...

ограничения по объёму я не вижу...

каждый товар в единственном экземпляре?...

(23 Май '21 19:43) all_exist

то что написано в таблице для меня загадка...

а Вас не устраивает решение методами динамического программирования?...

(23 Май '21 19:44) all_exist
1

доллары - цена ограничения по объему это вес да, для алгоритма не важно сколько экземпляров

динамическое программирование не полиномиально, я тут пытаюсь решить загадку тысячелетия P=NP путём нахождения полиномиального алгоритма решения для задачи о рюкзаке.

(23 Май '21 19:48) DarKProGameR

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

(23 Май '21 21:54) falcao

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

(23 Май '21 22:26) DarKProGameR

@DarKProGameR: я понимаю, к чему Вы стремитесь. Но, до тех пор, пока не найден общий подход, всё рассмотренное остаётся на уровне эмпирики и частных случаев. Ещё раз подчеркну, что нужно

1) общее описание алгоритма

2) доказательство того, что он находит оптимальное решение задачи

3) обоснование того, что алгоритм работает полиномиальное время.

(23 Май '21 22:40) falcao

Есть некое число O, являющееся ограничением рюкзака. Есть числа x в виде объёмов. n - порядок x

O=36,xn - "вес" вещей, тогда слева направо по отсортированной таблице идём по строке весов 1 с индексом 9 <= 36, тогда 36-1=35

Следующим по порядку идёт число 5 с индексом 7, тогда 35-5=30 (35 - новое число присвоенное О)

И так дальше по порядку, пока будет действительно условие О<=xn

Мне легче показать что у меня в черновике, чем описать это тут в тексте Но в черновике ещё страшнее.

Я проверял ответы с помощью неполиномиального алгоритма, совпадает везде, кроме случаев с ограничением 38 и 46

(23 Май '21 23:27) DarKProGameR

Было бы намного легче, если бы мне было с кем обсудить всё нормально, потому что в письменной форме это сущий кошмар.

(23 Май '21 23:29) DarKProGameR

@DarKProGameR: без того, что Вы называете "кошмаром", то есть без чёткого академического изложения, решение никем не будет признано, даже если оно есть. Таковы научные стандарты.

Но здесь пока рано о чём-то говорить: если Вы сами нашли контрпримеры, то алгоритм не подходит.

(24 Май '21 8:07) falcao

Я проведу больше тестов и найду причину появления этих контрпримеров. Возможно с алгоритмом не всё кончено, а я чего-то упустил.

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

(24 Май '21 11:42) DarKProGameR

Даже на старт не вышли еще.

(24 Май '21 12:29) spades

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

(24 Май '21 12:50) DarKProGameR

@DarKProGameR: математики решают эту проблему в течение более чем 50 лет :) Боюсь, что у Вас искажённое представление о потраченном времени.

(24 Май '21 16:13) falcao
показано 5 из 15 показать еще 10
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,287
×295

задан
23 Май '21 16:42

показан
342 раза

обновлен
24 Май '21 19:58

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru