Форум программистов, компьютерный форум CyberForum.ru

Удаление подстрок из строки. Суммировать "вес" удаленных строк - C++

Восстановить пароль Регистрация
 
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 01:04     Удаление подстрок из строки. Суммировать "вес" удаленных строк #1
Думаю, что задача стандартная, и известна большинству программистам:

Дана строка s, а также набор подстрок, которые можно удалять из этой строки, причем каждая подстрока имеет свой "вес". При удалении подстроки к общему "весу" прибавляется "вес" удаленной подстроки. Нужно по заданной строке и набору найти максимальный вес, который можно набрать, удаляя подстроки из строки.

Например, есть строка abbcca, и заданы такие наборы ( через пробел стоимость подстроки ):
ab 10
bc 20
ca 2
aa 3
Ответом к этим данным есть вес 43 ( 2 раза подряд удаляем bc, потом aa ).

В общем, мне хотелось бы узнать, где можно прочитать про это, или услышать от кого-то алгоритм решения, спасибо!
P.S. Тема точно ДП (динамическое программирование).

Добавлено через 22 минуты
Ап - ап - ап...

Добавлено через 1 час 0 минут
Up up up
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.03.2012, 01:04     Удаление подстрок из строки. Суммировать "вес" удаленных строк
Посмотрите здесь:

удаление "строки" в бинарном файле C++
Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы C++
C++ я задал произвольный текст длинной 5 строк, и допустим что я ввел 5 раз букву "П" , какой цикл нужно создать чтобы пометять букву "П" на букву "Р" ?
C++ В заданном тексте удалить символ "," и подсчитать число удаленных символов
C++ Даны две строки. Если они начинаются с одинаковых символов, то напечатать "ДА", иначе - "НЕТ"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
absokolov
29 / 29 / 1
Регистрация: 10.05.2011
Сообщений: 120
16.03.2012, 02:02     Удаление подстрок из строки. Суммировать "вес" удаленных строк #2
А эти строки Вам откуда нужно получать?
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 10:47  [ТС]     Удаление подстрок из строки. Суммировать "вес" удаленных строк #3
A eto imeet znachenie? Cherez ifstream pust

Добавлено через 44 минуты
Эх...жду стоящих программистов...

Добавлено через 37 минут
Модераторы, прошу перенести мою тему в подраздел "С++ для экспертов", так как тут никто не знает, как решить этот вопрос, возможно, он не так и прост!

Добавлено через 1 час 2 минуты
Ап в сотый раз...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.03.2012, 12:33     Удаление подстрок из строки. Суммировать "вес" удаленных строк #4
Цитата Сообщение от AncinetHero Посмотреть сообщение
Ап в сотый раз...
ну не совсем в сотый...

Цитата Сообщение от AncinetHero Посмотреть сообщение
или услышать от кого-то алгоритм решения
предложу один алгоритм (может быть есть и лучше). На примере:
Цитата Сообщение от AncinetHero Посмотреть сообщение
Например, есть строка abbcca, и заданы такие наборы ( через пробел стоимость подстроки ):
ab 10
bc 20
ca 2
aa 3
Ответом к этим данным есть вес 43 ( 2 раза подряд удаляем bc, потом aa ).
итак имеем строку: 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.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 13:21  [ТС]     Удаление подстрок из строки. Суммировать "вес" удаленных строк #5
Большое спасибо за идею, сейчас попробую реализовать и сдать (есть задача на эту тему).

Но, я не вижу тут динамики, а тема как раз ДП, или она есть?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.03.2012, 13:58     Удаление подстрок из строки. Суммировать "вес" удаленных строк #6
Цитата Сообщение от AncinetHero Посмотреть сообщение
или она есть?
есть.
AncinetHero
49 / 49 / 3
Регистрация: 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() )
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
       vector < pair < string, int > > COMB;
       COMB.push_back( make_pair( "", 0 ) ); // у нас 1 пустая комбинация стоимостью 0
 
       for( i=0; i<l; i++ ){ // идем поочередно по каждому символу строки х
         int size_start = COMB.size(); // сейчас мы будем искать новые комбинации 
              //(см. пост №4) и добавлять их в конец этого же массива, 
              // и потому нужно запомнить начальную границу
 
         for( j=0; j<size_start; j++ ){ //
           COMB[j].first.push_back( X[i] ); // к каждой комбинации добавляем символ строки (за индекс отвечает первый цикл)
 
           for( k=0; k<n; k++ ){ // n - количество заданных подстрок (см. условие)
 
             int q = find( COMB[j].first.begin(), COMB[j].first.end(), C[k].first ) - COMB[j].first.begin(); 
             //ищем, есть ли в сочетании с индексом j рассматриваемая подстрока
 
             if( q < COMB[j].first.size() ){ // если есть
                 string temp = COMB[j].first;
                 temp.erase( COMB[j].first.begin() + q, COMB[j].first.begin() + q + C[k].first.length() );
             // удаляем ее
                 int w = find( COMB[j].first.begin(), COMB[j].first.end(), temp ) - COMB[j].first.begin();
            // проверяем, 
            // не пришли ли мы к такой комбинации раньше
 
                 if( w < COMB[j].first.size() ) // если не пришли
                   COMB.push_back( make_pair( temp, COMB[j].second + C[k].second ) ); // добавляем
             }
 
           }
 
         }
 
       }
Добавлено через 8 минут
Ошибку в реализации нашел .. на строке 9 нужно сделать while .. в коде до сих пор нет.

Добавлено через 3 минуты
Может кто то откомпилировать его у себя?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.03.2012, 22:36     Удаление подстрок из строки. Суммировать "вес" удаленных строк #8
AncinetHero, весь код покажите.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 22:41  [ТС]     Удаление подстрок из строки. Суммировать "вес" удаленных строк #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
     
main(){
       vector <int> cost( 27, -1 );
       int n, z, i, j, k, l;
       char c;
       string X;
       cin>>n;
       for( i=1; i<=n; i++ ){
            cin>>c>>z;
            cost[ c-'a'+1 ] = z;
       }
       cin>>X;
       l = X.length();
       cin>>n;
       vector < pair < string, int > > C( n+1 );
       for( i=1; i<=n; i++ ){
            cin>>C[i].first;
            for( j=0; j<C[i].first.length(); j++ )
              C[i].second += cost[ C[i].first[j]-'a'+1 ];
       }
       
       vector < pair < string, int > > COMB;
       COMB.push_back( make_pair( "", 0 ) );
       for( i=0; i<l; i++ ){
         int size_start = COMB.size();
         for( j=0; j<size_start; j++ ){\
           COMB[j].first.push_back( X[i] );
           for( k=0; k<n; k++ ){
             int q = find( COMB[j].first.begin(), COMB[j].first.end(), C[k].first ) - COMB[j].first.begin();
             if( q < COMB[j].first.size() ){
                 string temp = COMB[j].first;
                 temp.erase( COMB[j].first.begin() + q, COMB[j].first.begin() + q + C[k].first.length() );
                 int w = find( COMB[j].first.begin(), COMB[j].first.end(), temp ) - COMB[j].first.begin();
                 if( w < COMB[j].first.size() )
                   COMB.push_back( make_pair( temp, COMB[j].second + C[k].second ) );
             }
           }
         }
       }
       for( i=0; i<COMB.size(); i++ )
         cout<<COMB[i].first<<" "<<COMB[i].second<<endl;
         
       system("pause");
     
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.03.2012, 23:15     Удаление подстрок из строки. Суммировать "вес" удаленных строк #10
Начиная отсюда неправильно:
C++
1
2
3
4
5
6
7
        int q = find( COMB[j].first.begin(), COMB[j].first.end(), C[k].first ) - COMB[j].first.begin();
             if( q < COMB[j].first.size() ){
                 string temp = COMB[j].first;
                 temp.erase( COMB[j].first.begin() + q, COMB[j].first.begin() + q + C[k].first.length() );
                 int w = find( COMB[j].first.begin(), COMB[j].first.end(), temp ) - COMB[j].first.begin();
                 if( w < COMB[j].first.size() )
                   COMB.push_back( make_pair( temp, COMB[j].second + C[k].second ) );
я же писал:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
- символ b . Перебираем наш текущие варианты и получаем (ab, 0). Проверяем от правого конца строки на наличие такого набора (обязательно от правого конца и необязательно набор должен покрывать всю строку).
Т.е. например текущий вариант:
(abccnfd, 0). И есть набор cnfd равный 10 (обратите внимание что он до правого конца доходит - это важно). В этом случае в текущие варианты добавится: (abc, 10)

А вот например текущий вариант:
(abccnfd, 0) и есть набор abc равный 10. В этом случае в текущие варианты не добавится ничего (хотя сама подстрока abc присутствует в строке abccnfd, но до правого конца не доходит).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2012, 23:25     Удаление подстрок из строки. Суммировать "вес" удаленных строк
Еще ссылки по теме:

C++ Описать класс "вещь", описывающий габариты и вес предмета
C++ Оператор "+", который должен суммировать 2 массива 2-х классов, выдает ошибку доступа
C++ Найти номер последней по порядку строки в матрице, содержащей наибольшее количество букв "ш", "щ"

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

Или воспользуйтесь поиском по форуму:
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 23:25  [ТС]     Удаление подстрок из строки. Суммировать "вес" удаленных строк #11
Нереальный алгоритм) Может и получится написать, но он 100% не оптимальный
Yandex
Объявления
16.03.2012, 23:25     Удаление подстрок из строки. Суммировать "вес" удаленных строк
Ответ Создать тему
Опции темы

Текущее время: 09:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru