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

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

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

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

30.05.2012, 00:29. Просмотров 508. Ответов 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++
Здравствуйте. Допустим, есть у меня 2 числа (до 1000, например). Как мне перебрать все возможные комбинации произведений этих чисел? ...

Перебор значений - C++
Вывести на экран в возрастающем порядке все трехзначные числа, в десятичной записи которых нет одинаковых цифр.

Перебор комбинаций - C++
Доброго времени суток. Нашел в сети картинку - генератор речей. 4 столбика по 6 фраз в каждом. При переборе слева направо получается...

Перебор списка - C++
Всем привет. Задача: Перебрать все элементы списка(линейный однонаправленный), так что бы поучаствовали все элементы, но не было повторов...

Перебор комбинаций - C++
Здравствуйте! Возникла такая задача. Дан одномерный массив из N цифр,нужно составить все возможные комбинации чисел из этих цифр(числа...

Cделать перебор id-ов - C++
есть ссылка: http//:fafaf.ru/index.php?id=1000 нужно сделать перебор id ов как это замутить? в цикле сделать перебор и...

Перебор матриц - C++
День добрый. Очень нужна помощь с написанием отдельного фрагмента программы. Задаётся размерность матрицы m, нужно поочерёдно перебирать...

Полный перебор - C++
Дано множество целых чисел. Требуется разбить множество на две части суммы элементов которых равны. Если нельзя провести разбиение, выдать...

Перебор текста - C++
Доброго времени суток, мне нужно написать функцию перебора строки, на обнаружение команд. искал про XML но так и ничего путного не нашел,...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Модератор
Эксперт CЭксперт С++
7171 / 4337 / 633
Регистрация: 29.11.2010
Сообщений: 11,784
30.05.2012, 00:33     Нетривиальный прямой перебор #2
Функция из STL - std::next_permutation
Ответ Создать тему
Опции темы

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