Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Kanimas
0 / 0 / 0
Регистрация: 02.03.2019
Сообщений: 1
1

Не получается реализовать алгоритм

02.03.2019, 15:12. Просмотров 164. Ответов 1

Попалась задача на реализацию алгоритма, уже несколько дней бьюсь головой об стену, потому что ничего нормального придумать так и не смог. Из ограничений: время работы не более 1 секунды.

В магазине каждый товар имеет цену. Например, цена одного цветка равна $2, а цена одной вазы равна $5. Чтобы привлечь покупателей, магазин ввёл скидки. Скидка заключается в том, чтобы продавать набор одинаковых или разных товаров по пониженной цене. Примеры: три цветка за $5 вместо $6, или две вазы вместе с одним цветком за $10 вместо $12.

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

Для описанных выше цен и скидок наименьшая цена за три цветка и две вазы равна $14: две вазы и один цветок продаются по сниженной цене за $10 и два цветка — по обычной цене за $4.

Формат входных данных
Вначале файла описываются покупки («корзина с покупками»).
Первая строка содержит число b (0 ≤ b ≤ 5) различных видов товара в корзине.

Каждая из следующих b строк содержит три целых числа x, k и p, где x — уникальный код товара (1 ≤ x ≤ 999); k — число единиц товара c кодом x, которое должно находится в корзине (1 ≤ k ≤ 5); p — стоимость единицы товара с кодом x (1 ≤ p ≤ 9999). Обратите внимание, что общее число товаров в корзине может быть не более 5 × 5 = 25 единиц.

Затем описываются скидки, которые действуют в магазине. В отдельной строке записано число s скидок (0 ≤ s ≤ 99).

Каждая из следующих s строк описывает одну скидку, определяя набор товаров и общую стоимость набора. Первое число n в такой строке определяет число различных видов товара в наборе (1 ≤ n ≤ b). Следующие n пар (x, k) чисел указывают, что k единиц товара с кодом x включены в набор для скидки (1 ≤ k ≤ 5, 1 ≤ x ≤ 999). Гарантируется, что уникальный код x товара ранее встречался в описании товаров, которые нужно купить. Последнее число p в строке определяет сниженную стоимость набора (1 ≤ p ≤ 9999). Стоимость набора меньше суммарной стоимости отдельных единиц товаров в наборе.

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

Пример
discount.in
2
7 3 2
8 2 5
2
1 7 3 5
2 7 1 8 2 10

discount.out
14

Замечание
Поясним приведённый пример.
Необходимо купить три единицы товара с кодом №7, причём можно купить их по цене $2 за единицу, и две единицы товара с кодом №8, причём без скидок их можно купить по цене $5 за единицу.

В магазине действуют скидки. Так, набор из трёх единиц товара с кодом №7 стоит $5. Набор из двух товаров кодами №7 (одной единицы) и №8 (двух единиц) продаётся по скидке за $10. В данном случае оптимально воспользоваться второй скидкой, потратив $10, и докупить по отдельности две единицы товара №7 за 2 × $2 = $4.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.03.2019, 15:12
Ответы с готовыми решениями:

Не получается реализовать программу
Нужно написать программу, которая будет определять принадлежность заданной точки декартовой...

Не получается составить алгоритм вычисления
Здравствуйте, уважаемые программисты! К сожалению, я ни капли не знаю этот Java, а нужно решить...

Не получается реализовать функцию вывода информации из ArrayList
Как и сказано в названии темы, не получается реализовать функцию вывода информации из ArrayList. ...

Не получается выводить данные динамически, подскажите, пожалуйста, как реализовать.
есть такой код: while ((line = outReader.readLine()) != null) { //чтение выходного...

Адаптивный (динамический) алгоритм Хаффмана: Не получается реализовать функцию обновления дерева
Всем привет При реализации сабжа столкнулся с проблемой того, как задать дерево Хаффмана. ...

1
Aviz__
805 / 597 / 161
Регистрация: 17.02.2014
Сообщений: 3,526
04.03.2019, 11:22 2
Kanimas, попроси перенести тему сюда http://www.cyberforum.ru/algorithms/
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.03.2019, 11:22

Не получается реализовать
Дана целочисленная квадратная матрица. Определить: 1) сумму элементов в тех строках, которые не...

Не получается реализовать парсинг
Всем привет, пишу свой миниантивирус. Вот никак не могу додуматься как реализовать парс с файла....

Не получается реализовать BackgroundWorker
amespace WindowsFormsApplication2 { public partial class Form1 : Form { public...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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