Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757
Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770
Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737 Форумы портала PHP.SU :: Вопрос к программистам [6]
----- Правильный вопрос - уже половина правильного ответа!
p.s. индусы повсюду, будьте осторожны!
EuGen
Отправлено: 25 Июля, 2013 - 14:11:40
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Одна из классических задач по упаковке.
Существует некоторый контейнер с максимальной грузоподъёмностью W. Существует N грузов ei. Каждый груз имеет две характеристики - вес wi и стоимость vi (1 < i <= N). Считаем, что геометрические особенности грузов и контейнера несущественны, и единственная характеристика - это вес. Набор предметов может быть помещён в контейнер, если суммарный вес набора не превышает W. Каждый предмет можно выбрать только один раз.
Дан входной набор данных для грузов ei, который представляет собой массив из пар значений - веса предмета wi и стоимости предмета vi - пусть для определённости это будет реализовано как ассоциативный массив с ключами weight и value. Дано также число W. Все значения весов и стоимостей, а также грузоподъёмность контейнера W - являются положительными целыми числами.
Для определённости также считаем, что 0 < W <=100 и 0 < wi <=100 (то есть все веса предметов, а также грузоподъёмность контейнера больше нуля и меньше либо равны 100).
Далее, количество грузов N тоже положительно (не может быть пустого набора) и не превышает 1E5 Требуется - по данному набору предметов {ei} и числу W найти число V, которое является максимальной суммарной стоимостью предметов, которые удалось поместить в контейнер (сумма весов этих предметов не превышает W) - то есть написать функцию getMaxValue, принимающую два параметра - набор грузов и величину W, и возвращающую единственное целое число V - максимально достижимую стоимость набора предметов, которые можно поместить в контейнер.
Пример:
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
VenZell
Отправлено: 25 Июля, 2013 - 14:17:31
Частый гость
Покинул форум
Сообщений всего: 237
Дата рег-ции: Июнь 2013
Помог: 12 раз(а)
soffrick, парные скобки из строки удаляются, остаются только те, что остались без пары. Соответственно, если выходная строка пуста - все скобки правильно закрыты. Отсюда такое условие. upd: понял, где косяк.
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
Мелкий
Сделать можно. Плохо масштабируется на другое число скобок (и/или другие пары), разумеется. Вообще обработать строку регулярным выражением до работы проверки корректности расстановки скобок - идея хорошая, поскольку позволяет сократить объем работы, вероятно, на порядки.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
nerv
Отправлено: 17 Августа, 2013 - 21:16:10
Посетитель
Покинул форум
Сообщений всего: 407
Дата рег-ции: Февр. 2013 Откуда: Россия
На самом деле, я не ожидаю, что кто-либо даст достаточно точный ответ, но мне интересен ход мыслей. Вопрос можно отнести к весьма сложным, поскольку для ответа на него нужны специальные знания.
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
LIME
Отправлено: 25 Сентября, 2013 - 16:55:51
Активный участник
Покинул форум
Сообщений всего: 10732
Дата рег-ции: Нояб. 2010
Помог: 322 раз(а)
мне кажется дело в отложенном копировании
?
EuGen
Отправлено: 25 Сентября, 2013 - 16:56:42
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
LIME пишет:
мне кажется дело в отложенном копировании
Нет. Далеко от истины - и не поясняет разницы при применении "@" (см. hint0 - впрочем, ответа нет ни в одном из hint)
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
SAD
Отправлено: 25 Сентября, 2013 - 16:57:31
Постоянный участник
Покинул форум
Сообщений всего: 2508
Дата рег-ции: Май 2009 Откуда: Днепропетровск, Украина
Помог: 75 раз(а)
мозг бдыщь
imya
Отправлено: 25 Сентября, 2013 - 16:57:50
Участник
Покинул форум
Сообщений всего: 1472
Дата рег-ции: Сент. 2012 Откуда: Запорожье, Украина
Когда нормальный человек, уезжая из дома одевает на жену пояс верности, веб-дизайнер ставит на нее счетчик...
EuGen
Отправлено: 25 Сентября, 2013 - 16:59:53
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
imya пишет:
из-за посткремента ?
Из-за постинкремента что?
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
imya
Отправлено: 25 Сентября, 2013 - 17:03:36
Участник
Покинул форум
Сообщений всего: 1472
Дата рег-ции: Сент. 2012 Откуда: Запорожье, Украина
Помог: 19 раз(а)
EuGen пишет:
Из-за постинкремента что?
Получается одинаковый результат.
Ведь если написать ++$x(прекремент) , то произойдёт операция $х = $х+1, а потом уже остальные действия. В случае же с $x++(посткремент), вначале выполнятся действия, предшествующие операции, а после уже $х=$х+1.
Когда нормальный человек, уезжая из дома одевает на жену пояс верности, веб-дизайнер ставит на нее счетчик...
LIME
Отправлено: 25 Сентября, 2013 - 17:05:30
Активный участник
Покинул форум
Сообщений всего: 10732
Дата рег-ции: Нояб. 2010
Помог: 322 раз(а)
постинкремент создает временную переменную
а преинкремент увеличивает настоящую
но как бы и что?))
EuGen
Отправлено: 25 Сентября, 2013 - 17:05:42
Профессионал
Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007 Откуда: Berlin
Помог: 707 раз(а)
imya пишет:
Или я неправ?
Нет. Это не поясняет ничего - то есть вопрос остаётся в силе - вне зависимости от того, как работает постинкремент, нужно понять, почему в первом случае слагаемых два (и один постинкремент), а во втором - три (и снова постинкремент один и на той же позиции), но результат одинаковый. И, как бонус - почему при применении "@" в первом случае результат меняется (и почему на 2)
----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
Все гости форума могут просматривать этот раздел. Только зарегистрированные пользователи могут создавать новые темы в этом разделе. Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.