50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
1 | |
Удаление подстрок из строки. Суммировать "вес" удаленных строк16.03.2012, 01:04. Показов 1239. Ответов 10
Метки нет (Все метки)
Думаю, что задача стандартная, и известна большинству программистам:
Дана строка s, а также набор подстрок, которые можно удалять из этой строки, причем каждая подстрока имеет свой "вес". При удалении подстроки к общему "весу" прибавляется "вес" удаленной подстроки. Нужно по заданной строке и набору найти максимальный вес, который можно набрать, удаляя подстроки из строки. Например, есть строка abbcca, и заданы такие наборы ( через пробел стоимость подстроки ): ab 10 bc 20 ca 2 aa 3 Ответом к этим данным есть вес 43 ( 2 раза подряд удаляем bc, потом aa ). В общем, мне хотелось бы узнать, где можно прочитать про это, или услышать от кого-то алгоритм решения, спасибо! P.S. Тема точно ДП (динамическое программирование). Добавлено через 22 минуты Ап - ап - ап... Добавлено через 1 час 0 минут Up up up
0
|
16.03.2012, 01:04 | |
Ответы с готовыми решениями:
10
Удаление подстрок из массива строк Удаление повторных вхождений подстрок из строк Удаление подстрок из строки Удаление несколько подстрок из строки |
31 / 31 / 3
Регистрация: 10.05.2011
Сообщений: 120
|
|
16.03.2012, 02:02 | 2 |
А эти строки Вам откуда нужно получать?
0
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
16.03.2012, 10:47 [ТС] | 3 |
A eto imeet znachenie? Cherez ifstream pust
Добавлено через 44 минуты Эх...жду стоящих программистов... Добавлено через 37 минут Модераторы, прошу перенести мою тему в подраздел "С++ для экспертов", так как тут никто не знает, как решить этот вопрос, возможно, он не так и прост! Добавлено через 1 час 2 минуты Ап в сотый раз...
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
16.03.2012, 12:33 | 4 |
ну не совсем в сотый...
предложу один алгоритм (может быть есть и лучше). На примере: итак имеем строку: abbcca. Что бы было понятней введу понятие текущие варианты - изначально их нет. Итак перебираем символы из заданной строки: - символ a . Т.к. текущих вариантов нет, то добавляем к ним только (a, 0) - строка и набранные очки. - символ b . Перебираем наш текущие варианты и получаем (ab, 0). Проверяем от правого конца строки на наличие такого набора (обязательно от правого конца и необязательно набор должен покрывать всю строку). Такой набор есть, поэтому добавляем к текущим вариантам (, 10) - пустая строка и набранные очки. Итого в текущих вариантах: (ab, 0) и (, 10) - символ b . Получаем в текущих вариантах: (abb, 0) и (b, 10) - символ c . Получаем в текущих вариантах: (abbc, 0), из которого получаем еще один (ab, 20). Также получаем (bc, 10) из которого получаем (, 30) . Итого в текущих вариантах имеем: (abbc, 0), (ab, 20), (bc, 10), (, 30). - символ с . Получаем в текущих вариантах: (abbcc, 0), (abc, 20), из которого получаем еще и (a, 40), получаем (bcc, 10), (c, 30). Итого в текущих вариантах: (abbcc, 0), (abc, 20), (a, 40), (bcc, 10), (c, 30). - символ a . Получаем: (abbcca, 0) из котрого получаем еще и (abbc, 2), (abca, 20) из которого получаем еще и (ab, 20), (aс, 40) из которого получаем еще и (, 43), (bcca, 10) из которого получаем еще и (bc, 12), (ca, 30) из которого получаем еще и (, 32). По окончании прохода ищем максимальное число в текущих вариантах. В данном случае это 43.
1
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
16.03.2012, 13:21 [ТС] | 5 |
Большое спасибо за идею, сейчас попробую реализовать и сдать (есть задача на эту тему).
Но, я не вижу тут динамики, а тема как раз ДП, или она есть?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
16.03.2012, 13:58 | 6 |
0
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
||||||
16.03.2012, 22:25 [ТС] | 7 | |||||
Где? Здесь обычный цикл, никаких просчетов делать не надо. Тогда задачу "найти сумму чисел в массиве" тоже динамикой можно считать
Добавлено через 8 часов 12 минут На досуге, пожалуйста, попробуйте проверить этот кусок кода, у меня выдает ошибку в библиотеке STD. В коде ошибку не вижу Тут C[i].first - подстрока, которую можно удалить, C[i].second - ее стоимость. i = 0..n COMB[i].first - комбинация(идея поста №4), COMB[i].second - ее стоимость. i = 0..COMB.size() x - строка размером l ( l=x.length() )
Ошибку в реализации нашел .. на строке 9 нужно сделать while .. в коде до сих пор нет. Добавлено через 3 минуты Может кто то откомпилировать его у себя?
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
16.03.2012, 22:36 | 8 |
AncinetHero, весь код покажите.
0
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
||||||
16.03.2012, 22:41 [ТС] | 9 | |||||
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
16.03.2012, 23:15 | 10 | |||||
Начиная отсюда неправильно:
Т.е. например текущий вариант: (abccnfd, 0). И есть набор cnfd равный 10 (обратите внимание что он до правого конца доходит - это важно). В этом случае в текущие варианты добавится: (abc, 10) А вот например текущий вариант: (abccnfd, 0) и есть набор abc равный 10. В этом случае в текущие варианты не добавится ничего (хотя сама подстрока abc присутствует в строке abccnfd, но до правого конца не доходит).
1
|
50 / 50 / 12
Регистрация: 22.05.2011
Сообщений: 326
|
|
16.03.2012, 23:25 [ТС] | 11 |
Нереальный алгоритм) Может и получится написать, но он 100% не оптимальный
0
|
16.03.2012, 23:25 | |
16.03.2012, 23:25 | |
Помогаю со студенческими работами здесь
11
Удаление всех подстрок из строки Обработка строк по условию, получение подстрок из строки! Консультация С увеличением найденых и соответственно удаленных строк, время удаления строки увеличивается. Обработка строк. Признак окончания ввода строки. Удаление слов из строк Удаление подстрок Удаление конкретной строки из списка строк, при этом не трогать дублирующие строки Удаление конкретной строки из списка строк, при этом не трогать дублирующие строки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |