Дистанционная подготовка: краткий алгоритм подскажите пожалуйста!!
краткий алгоритм подскажите пожалуйста!!
от Айдар Омурбеков - Пятница 1 Июль 2011, 19:24
1623. Пицца
  краткий алгоритм подскажите пожалуйста!!
не представляю как решать эту задачку
Re: краткий алгоритм подскажите пожалуйста!!
от Dima Svetov - Понедельник 14 Апрель 2014, 22:38
  может кому-нибудь поможет)

сначала рассмотрим частные случаи
а > c  значит, что пицца итак дороже, чем с  => доставка бесплатна ответ : a
а + b <= c значит, что выгоднее просто заказать пиццу + доставку, чем добивать сумму до с


динамика у меня была такая, может можно что-то интереснее

dp[количество предметов][стоимость] = 1 либо 0
(можно или нельзя набрать)

в первом цикле перебираем предметы тк их у нас фиксированное число

во 2 цикле подгоняем стоимости так же как в рюкзаке:
у нас два варианта либо включать предмет(если он не превышает текущую стоимость) либо нет.
Иначе говоря dp[i][j] мы можем получить либо из
dp[i-1][j] - тоесть такая же стоимость при меньшем колич. предметов(при условии что она существует dp[i-1][j] = 1)
либо из dp[i-1][j-d[i]]

теперь надо найти значение динамики, это будет первое значение(тоесть минимальное значение которое при использовании всех предметов, которое удовлетворяет условию) которое существует в d[n][i] i = 1..b

если такого нет значит ответом будет а+b

остается восстановить ответ




Re: краткий алгоритм подскажите пожалуйста!!
от Никита Пушкин - Четверг 7 Август 2014, 20:17
  Что-то вообще ничерта не понятно у тебя в решении. Например, что именно ты делаешь в первом цикле? И как ты будешь подгонять стоимости, если тут вообще другой принцип?
В общем, буду признателен, если кто-нибудь объяснит мне, как все же решить эту задачу. И можно ли здесь обойтись одним циклом?