Неприятность здесь в том, что формулировка неверная, это не set, а multiset ... который, в свою очередь, создаёт неприятности.Встретилось задание из раздела о динамическом программировании, которое вызывает у меня трудности. Необходимо построить алгоритм, который по заданному множеству определяет, можно ли его разбить на три части, в которых суммы всех элементов будут равны. Например:
[1, 2, 3, 4, 4, 5, 8] -> {1,8}, {4,5}, {2,3,4}
Очевидно, что если сумма всех элементов не делится на 3, то множество не содержит такого разбиения (самая простая часть:) ). Но как действовать дальше?
Лучше бы здесь говорить о списке чисел!
Вот рабочее решение ... более-менее:
Код: Выделить всё
#include <iostream>
#include <sstream>
#include <set>
#include <cstdlib>
using namespace std;
ostream& operator <<( ostream& out, const multiset<int>& obj ) {
out << "{ ";
for( auto i = obj.begin(); i != obj.end(); i++ ) {
auto j = i;
j++;
out << *i << ( j == obj.end() ? "" : ", " );
}
return out << " }";
}
istream& operator >>( istream& inp, multiset<int>& obj ) {
obj.clear();
string e;
while( true ) {
getline( inp, e );
if( inp.rdstate() & ios::eofbit ) break;
if( 0 == e.length() ) break;
istringstream ist( e );
try {
double d;
while( ist >> d )
obj.insert( d );
}
catch( exception const& e ) {
cout << "ошибка ввода!" << endl;
exit( 1 );
}
}
return inp;
};
multiset<int>& operator +=( multiset<int>& md, const multiset<int>& ms ) {
for( auto i = ms.begin(); i != ms.end(); i++ )
md.insert( *i );
return md;
}
multiset<int>& operator -=( multiset<int>& md, const multiset<int>& ms ) {
for( auto i = ms.begin(); i != ms.end(); i++ ) {
int n = md.count( *i );
if( 0 == n ) continue;
auto j = md.find( *i );
if( j != md.end() )
md.erase( *i );
while( --n > 0 ) md.insert( *i );
}
return md;
}
int summa( const multiset<int>& obj ) {
int ret = 0;
for( auto i = obj.begin(); i != obj.end(); i++ )
ret += *i;
return ret;
}
multiset<int> select( multiset<int> from, int sum ) {
multiset<int> s1;
for( auto i = from.rbegin(); i != from.rend(); i++ ) {
if( *i == sum ) {
s1.insert( *i );
return s1;
}
if( *i < sum ) {
multiset<int> from1( from );
auto j = from1.find( *i );
from1.erase( j );
multiset<int> s2 = select( from1, sum - *i );
if( !s2.empty() ) {
s1.insert( *i );
s1 += s2;
return s1;
}
}
}
return s1;
}
int main() {
multiset<int> S;
cout << "Вводите числа построчно (пустая строка - конец ввода):" << endl;
cin >> S;
cout << S << " ->" << endl;
if( summa( S ) % 3 != 0 )
cout << "нет требуеого разбиения" << endl;
int sum = summa( S ) / 3;
multiset<int> S1, S2, S3;
cout << ( S1 = select( S, sum ) ) << endl;
cout << ( S2 = select( ( S -= S1 ), sum ) ) << endl;
cout << ( S3 = select( ( S -= S2 ), sum ) ) << endl;
}
Код: Выделить всё
olej@nvidia ~/2015_WORK/in.WORK/SchoolCPP/3set $ ./3set
Вводите числа построчно (пустая строка - конец ввода):
1 2 3 4
4 5 8
{ 1, 2, 3, 4, 4, 5, 8 } ->
{ 1, 8 }
{ 4, 5 }
{ 2, 3, 4 }