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

Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. - C++

Восстановить пароль Регистрация
 
projest
0 / 0 / 0
Регистрация: 16.02.2014
Сообщений: 2
17.02.2014, 10:52     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. #1
Добрый день. Задали такое задание:

Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.

Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.

Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.

N<100. Количество наборов для каждого чиновника не превосходит 15.

Огромная просьба написать код. Если трудно, хотя бы обьяснить алгоритм что нужно сделать) Заранее спасибо)

Добавлено через 21 час 52 минуты
Актуально(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.02.2014, 10:52     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.
Посмотрите здесь:

Необходимо создать минимальный проект-образец в DEV C++ C++
Массивы, нужно определить минимальный элемент, вывести его значение и индекс... C++
C++ Разработать программу «Стоимость компьютера», позволяющую вычислять стоимость комплекта для АРМ различных специалистов
Разработать программу «Стоимость компьютера», позволяющую вычислять стоимость комплекта для АРМ различных специалистов C++
Вычисление степени, в которую необходимо возвести 2 для получения числа, которое <= заданному числу C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ryuk
 Аватар для Ryuk
179 / 177 / 33
Регистрация: 10.06.2011
Сообщений: 869
17.02.2014, 11:00     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. #2
projest, о том что нужно делать написано у вас в задании. Выкладывайте свои наработки, говорите что не получается и старайтесь сделать что-то самим. Иначе вы здесь долго будете ожидать помощи, тем более с подобной задачей.
stikkas
 Аватар для stikkas
19 / 19 / 6
Регистрация: 26.01.2014
Сообщений: 56
17.02.2014, 13:40     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. #3
Цитата Сообщение от projest Посмотреть сообщение
Огромная просьба написать код. Если трудно, хотя бы обьяснить алгоритм что нужно сделать)
берешь взятку и несешь тому, кто тебе эту задачу задал
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
18.02.2014, 15:17     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. #4
нужно уметь писать простую динамику на дереве.
в задаче говорится, что система чиновников образует дерево. приглядитесь, там об этом говорится) вот здесь:
Цитата Сообщение от projest Посмотреть сообщение
У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.
вопрос на понимание: кто представляет собой корень дерева.
ну теперь напишем динамику на дереве прям по определению. для каждой вершины известно множество переходов - взятка + набор чиновников. будем считать ответ в порядке обхода в глубину. выбираем для каждой вершины лучший для нас вариант перехода. потом, пользуясь этим ответом считаем ответ для вершины-родителя(т.е. начальника). ну и так придем к общему ответу.
farced
 Аватар для farced
18 / 18 / 12
Регистрация: 03.05.2016
Сообщений: 90
13.10.2016, 15:07     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. #5
Используй стек
Так как могут быть потребованы подписи лишь непосредственных подчиненных, то для любого разумного способа получения лицензии подпись всех подписавших чиновников, кроме первого, используются в одном и только одном наборе. Таким образом, мы можем определить стоимость подписи любого чиновника как минимум по соответствующим ему набором сумм стоимостей подчиненных и взятии для набора. Таким образом, мы получаем простой и эффективный рекурсивный алгоритм определения стоимостей чиновников.

Но у этой задачи есть маленький подводный камень, а именно, должно быть заведено глобальное множество уже пройденных чиновников, что исключает повторную обработку этих чиновников. Сложность алгоритма - линейна по суммарному числу элементов в наборе.
Yandex
Объявления
13.10.2016, 15:07     Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.
Ответ Создать тему
Опции темы

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