Добрый день, подскажите, куда копать.

Есть гриф штанги, весит 5 кг.
Есть диски для грифа:
5 кг 2 штуки
10 кг 2 штуки
15 кг 2 штуки

Задача: определить диапазон весов штанги (гриф+диски).
То есть от 0 кг до 200 кг.

Должно выйти:

5 кг - только гриф
15 кг - диски по 5 кг
25 кг - диски по 10 кг
35 кг - диски по 15 кг
35 кг - диски по 10 кг + диски по 5 кг
40 кг - диски по 15 кг + диски по 5 кг
55 кг - диски по 15 кг + диски по 10 кг
65 кг - диски по 15 кг + диски по 10 кг + диски по 5 кг

С помощью линейного программирования можно решить задачу, задав вопрос,
"доступен ли вес 10,15,15.5,16,17... 50.5 кг у штанги".
Таким образом определяется оптимальное сочетание дисков для конкретного веса, но не все возможные комбинации (можно, конечно, в цикле пройтись по всем весам, но это очень дорого для производительности).

  1. А вот какая задача может именно быстро определить возможные сочетания (может, комбинаторика)?
  2. Хотелось бы добавить еще ограничения, вроде толщины диска и свободного места на грифе, чтобы 100% корректные значения выдавал. Это уже программирование с эвристикой будет или есть подходящие алгоритмы и задачи классические?

задан 19 Сен '14 1:33

изменен 19 Сен '14 11:54

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
0

1) Для чисел такого простого вида всё достаточно очевидно. Общий вес составляет $%5+10x+20y+30z=5+10(x+2y+3z)$%, где $%x$%, $%y$%, $%z$% -- переменные, принимающие значение 0 или 1 (0, если мы не берём диски данного типа, и 1, если берём).

Понятно, что при таких условиях выражение $%x+2y+3z$% может принимать все целые значения от 0 до 6. При этом значение 3 можно получить двумя способами. Вес штанги при этом будет принимать значения 5, 15, 25, 35, 45, 55, 65 (40 не может быть -- там надо добавить гриф).

Задачи такого вида при более сложных данных можно решать при помощи комбинаторных методов типа рассмотрения производящих функций. При этом перемножается несколько многочленов, и по коэффициентам можно определить, сколькими способами получается заданное число. Скажем, выражению $%x+2y+3z$% соответствовала бы п.ф. $%(1+t)(1+t^2)(1+t^3)=1+t+t^2+2t^3+t^4+t^5+t^6)$%. Если бы коэффициент при какой-то степени $%t^d$% была равен нулю, то это означало бы, что такое число из слагаемых не составить. А если коэффициент равен 2, то способов два. Правда, я не думаю, что для решения простых задач это уместно, если ручной перебор не представляет труда.

2) Здесь сначала надо чётко поставить математическую задачу. Если я правильно уловил идею, то там будут ограничения в виде неравенств. Типа того, что много толстых дисков не уместятся на грифе. Алгоритмы для решения таких задач есть всегда (чисто переборные), и при небольшом числе данных это всё быстро можно посчитать на компьютере. Вопрос же о том, как это всё себя повело бы при больших объёмах данных, надо анализировать отдельно. Этим занимается специальная теория, относящаяся к вычислительной сложности дискретных задач.

ссылка

отвечен 19 Сен '14 3:13

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,924

задан
19 Сен '14 1:33

показан
843 раза

обновлен
19 Сен '14 3:13

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

по почте:

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

по RSS:

Ответы

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

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