Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
floke
0 / 0 / 0
Регистрация: 02.05.2012
Сообщений: 4
#1

Нетривиальный прямой перебор - C++

30.05.2012, 00:29. Просмотров 498. Ответов 1
Метки нет (Все метки)

Собстевенно g++, QT.

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

Есть 7 видов гирек разной массы для весов. Веса гирек 0.3 0.6 ... 2.5(возможны любые, не суть). Требуется перебрать всевозможные варианты установки гирек на весы. Общая масса установленных гирек не должна превышать 25 кг, при этом не должна быть менее 22.5. На весах одновременно может находиться несколько гирек одного вида. Каждая гирька при этом имеет цену(условно, чтобы установить гирьку на весы, мы её сначала должны купить, причем цена зависит от последовательности покупки/установки гирьки, что то вроде скидки за каждую последующую покупку). Важна не только общая масса гирек но и последовательность установки(то есть например первой ставим гирьку массой 0.3, второй 0.6 - считаем общую цену за две гирьки, потом ставим третью гирьку - пересчитываем цену и тд). Ещё раз повторюсь, цена за гирьки постоянно меняется и зависит от предыдущих покупок. Необходимо прямым перебором найти всевозможные точки вес/цена.

Всё это дело предполагается занести в map, после чего с шагом массы 0.1 искать максимальное/минимальное значение цены для текущей массы(если такая масса вообще существует, например массы 0.2 на весах быть не может, ибо минимальная гирька весит 0.3).

Вопрос: каким образом можно решить поставленную задачу? Подвох в том, что каждый элемент может быть установлен не 1 раз, те 7 вложенных циклов не прокатит, можно попробовать рекурсию, но как тогда отслеживать варианты???

Может быть есть готовая функция/библиотека(например слышал о функции из STL, которая осуществляет прямой перебор вариантов символов из слова) для подобных задач?

Понимаю, что расчет будет долгим, но требуется именно прямой перебор.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2012, 00:29     Нетривиальный прямой перебор
Посмотрите здесь:

Перебор матриц C++
C++ Полный перебор
Перебор списка C++
C++ Перебор комбинаций
Перебор C++
C++ Найти и вывести на экран наибольший нетривиальный делитель числа
C++ Перебор символов
Перебор значений C++
C++ перебор значений
Перебор комбинаций C++
C++ Cделать перебор id-ов
Перебор C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт CЭксперт С++
 Аватар для MrGluck
6227 / 3472 / 424
Регистрация: 29.11.2010
Сообщений: 9,178
30.05.2012, 00:33     Нетривиальный прямой перебор #2
Функция из STL - std::next_permutation
Yandex
Объявления
30.05.2012, 00:33     Нетривиальный прямой перебор
Ответ Создать тему
Опции темы

Текущее время: 22:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru