PHP.SU

Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (9): « 1 2 3 4 5 [6] 7 8 9 »   

> Описание: Комбинаторика, алгоритмы и прочее - в программном коде
soffrick
Отправлено: 25 Июля, 2013 - 14:10:04
Post Id



Посетитель


Покинул форум
Сообщений всего: 381
Дата рег-ции: Май 2012  
Откуда: Россия, Москва


Помог: 17 раз(а)





VenZell
PHP:
скопировать код в буфер обмена
  1. return empty($clean_str) ? true : false;

зачем так? Улыбка


-----
Правильный вопрос - уже половина правильного ответа!

p.s. индусы повсюду, будьте осторожны!
 
 Top
EuGen Администратор
Отправлено: 25 Июля, 2013 - 14:11:40
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 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 - максимально достижимую стоимость набора предметов, которые можно поместить в контейнер.
Пример:
PHP:
скопировать код в буфер обмена
  1. $rgData = [
  2.    ['weight'=>2, 'value'=>4],
  3.    ['weight'=>5, 'value'=>7],
  4.    ['weight'=>1, 'value'=>3],
  5.    ['weight'=>3, 'value'=>4]
  6. ];
  7. $iMaxWeight = 5;
  8. var_dump(getMaxValue($rgData, $iMaxWeight)); //8

вариант (Отобразить)


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
VenZell
Отправлено: 25 Июля, 2013 - 14:17:31
Post Id


Частый гость


Покинул форум
Сообщений всего: 237
Дата рег-ции: Июнь 2013  


Помог: 12 раз(а)





soffrick, парные скобки из строки удаляются, остаются только те, что остались без пары. Соответственно, если выходная строка пуста - все скобки правильно закрыты. Отсюда такое условие.
upd: понял, где косяк.

(Отредактировано автором: 25 Июля, 2013 - 14:30:06)

 
 Top
Мелкий Супермодератор
Отправлено: 16 Августа, 2013 - 11:54:38
Post Id



Активный участник


Покинул форум
Сообщений всего: 11868
Дата рег-ции: Июль 2009  
Откуда: Россия, Санкт-Петербург


Помог: 612 раз(а)




По задачке со скобками вариант. Как говорится, не делайте так, но так сделать можно:
Спойлер (Отобразить)


-----
PostgreSQL DBA
 
 Top
EuGen Администратор
Отправлено: 16 Августа, 2013 - 11:57:51
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Мелкий
Сделать можно. Плохо масштабируется на другое число скобок (и/или другие пары), разумеется. Вообще обработать строку регулярным выражением до работы проверки корректности расстановки скобок - идея хорошая, поскольку позволяет сократить объем работы, вероятно, на порядки.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
nerv
Отправлено: 17 Августа, 2013 - 21:16:10
Post Id



Посетитель


Покинул форум
Сообщений всего: 407
Дата рег-ции: Февр. 2013  
Откуда: Россия


Помог: 9 раз(а)




вариант со скобками (не самый оптимальный)

CODE (javascript):
скопировать код в буфер обмена
  1. function test( text ) {
  2.     var hash = { '(': 1, '[': 1, '{': 1, '}': -1, ']': -1, ')': -1 };
  3.     var position = { '(': 0, '[': 1, '{': 2, '}': 2, ']': 1, ')': 0 };
  4.     var index = text.length;
  5.     var result = [ 0, 0, 0 ];
  6.  
  7.     while( index-- ) {
  8.         var chr = text[ index ];
  9.         result[ position[ chr ] ] += hash[ chr ];
  10.  
  11.         if ( result[ position[ chr ] ] > 0 ) {
  12.             return false;
  13.         }
  14.     }
  15.  
  16.     return !result.filter(function( item ) { return item !== 0; }).length;
  17. }
  18.  
  19. console.log( 'abc([dy]*[dx]Fz)', test( 'abc([dy]*[dx]Fz)' ) );
  20. console.log( 'pqr[Gdz)/(Hdx]', test( 'pqr[Gdz)/(Hdx]' ) );
  21. console.log( 'foo', test( 'foo' ) );
  22. console.log( 'foo()', test( 'foo()' ) );
  23. console.log( ']', test( ']' ) );
  24. console.log( '(){[]}', test( '(){[]}' ) );


-----
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
 
 Top
EuGen Администратор
Отправлено: 25 Сентября, 2013 - 16:35:02
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




Поясните, почему в PHP следующие две программы дадут одинаковый результат (3) :

и


hint0 (Отобразить)


hint1 (Отобразить)


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
LIME
Отправлено: 25 Сентября, 2013 - 16:55:51
Post Id



Активный участник


Покинул форум
Сообщений всего: 10498
Дата рег-ции: Нояб. 2010  


Помог: 313 раз(а)




мне кажется дело в отложенном копировании
?


-----
DDD
 
 Top
EuGen Администратор
Отправлено: 25 Сентября, 2013 - 16:56:42
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




LIME пишет:
мне кажется дело в отложенном копировании

Нет. Далеко от истины - и не поясняет разницы при применении "@" (см. hint0 - впрочем, ответа нет ни в одном из hint)


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
SAD
Отправлено: 25 Сентября, 2013 - 16:57:31
Post Id



Постоянный участник


Покинул форум
Сообщений всего: 2511
Дата рег-ции: Май 2009  
Откуда: Днепропетровск, Украина


Помог: 75 раз(а)




мозг бдыщь
 
 Top
imya
Отправлено: 25 Сентября, 2013 - 16:57:50
Post Id



Участник


Покинул форум
Сообщений всего: 1473
Дата рег-ции: Сент. 2012  
Откуда: Запорожье, Украина


Помог: 19 раз(а)




EuGen , из-за посткремента ?


-----
PHP:
скопировать код в буфер обмена
  1. do {box != cat;} while (cat != box);


Когда нормальный человек, уезжая из дома одевает на жену пояс верности, веб-дизайнер ставит на нее счетчик...
 
My status
 Top
EuGen Администратор
Отправлено: 25 Сентября, 2013 - 16:59:53
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




imya пишет:
из-за посткремента ?

Из-за постинкремента что?


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
imya
Отправлено: 25 Сентября, 2013 - 17:03:36
Post Id



Участник


Покинул форум
Сообщений всего: 1473
Дата рег-ции: Сент. 2012  
Откуда: Запорожье, Украина


Помог: 19 раз(а)




EuGen пишет:
Из-за постинкремента что?


Получается одинаковый результат.

Ведь если написать ++$x(прекремент) , то произойдёт операция $х = $х+1, а потом уже остальные действия. В случае же с $x++(посткремент), вначале выполнятся действия, предшествующие операции, а после уже $х=$х+1.

Или я неправ?


-----
PHP:
скопировать код в буфер обмена
  1. do {box != cat;} while (cat != box);


Когда нормальный человек, уезжая из дома одевает на жену пояс верности, веб-дизайнер ставит на нее счетчик...
 
My status
 Top
LIME
Отправлено: 25 Сентября, 2013 - 17:05:30
Post Id



Активный участник


Покинул форум
Сообщений всего: 10498
Дата рег-ции: Нояб. 2010  


Помог: 313 раз(а)




постинкремент создает временную переменную
а преинкремент увеличивает настоящую
но как бы и что?))


-----
DDD
 
 Top
EuGen Администратор
Отправлено: 25 Сентября, 2013 - 17:05:42
Post Id


Профессионал


Покинул форум
Сообщений всего: 9097
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)




imya пишет:
Или я неправ?

Нет. Это не поясняет ничего - то есть вопрос остаётся в силе - вне зависимости от того, как работает постинкремент, нужно понять, почему в первом случае слагаемых два (и один постинкремент), а во втором - три (и снова постинкремент один и на той же позиции), но результат одинаковый. И, как бонус - почему при применении "@" в первом случае результат меняется (и почему на 2)


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
Страниц (9): « 1 2 3 4 5 [6] 7 8 9 »
Сейчас эту тему просматривают: 1 (гостей: 1, зарегистрированных: 0)
« Прочее »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
 



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB