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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
|
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
enum METHOD{ BACKTRACK, RECURSE } method = BACKTRACK; // Solution method
//======================================================================
vector<int> generateTest() // Does what it says on the can
{
// Some test vectors for debugging
// vector<int> V = { 2, 2, 3, 5 }; // No solution
vector<int> V = { 1, 2, 3, 4, 4, 5, 8 }; // Solution
// vector<int> V = { 1, 1, 1, 2, 2, 2 }; // Solution
// vector<int> V( 21, 1002 ); V[0] = 999; // Nasty case, no solution (optimisation up)
// vector<int> V( 21, 1002 ); V[0] = V[1] = V[2] = 999; // Balanced solution, but large array
// Or generate something random
// const int SIZE = 100; // Number of elements
// const int MAX = 30; // Maximum element value
// vector<int> V(SIZE);
// for ( int i = 0; i < SIZE; i++ ) V[i] = 1 + rand() % MAX;
return V;
}
//======================================================================
template<typename T> ostream &operator << ( ostream &strm, const vector<T> &V ) // Output a vector
{
for ( auto e : V ) strm << e << " ";
return strm;
}
//======================================================================
bool backtrack( int N, const vector<int> &TEST, vector<int> &remainder, vector<int> &PART )
{
int t = 0, p = 0; // t = index of element in TEST, p = partition number
while ( t < TEST.size() ) // Loop round trying to place successive elements of TEST
{
int value = TEST[t]; // Value to be placed
while( p < N ) // Loop round the untried partitions for this value
{
if ( value <= remainder[p] ) // If there is room to place it in this partition ...
{
remainder[p] -= value; // ... and update the sum
PART[t] = p; // ... and record which partition you've put it in
p = 0; // For next value, start again at first partition
t++; // Next position to be placed
break;
}
else
{
p++; // Otherwise try next partition
}
}
// If unplaced, have to BACK-TRACK by 1 and work from previous
if ( p == N ) // i.e. wasn't placed
{
t--; // So back up one position in T
if ( t < 0 ) return false; // No more possibilities of placement, so impossible
p = PART[t]; // The partition that element is currently in ...
remainder[p] += TEST[t]; // ... remove from that partition
p++; // Try to place in NEXT partition
}
}
return true;
}
//======================================================================
bool recurse( int N, const vector<int> &TEST, int t, vector<int> &remainder, vector<int> &PART )
{
// Base case
if ( all_of( remainder.begin(), remainder.end(), []( int a ) { return a == 0; } ) ) return true; // Successful
// Recursion
int value = TEST[t]; // Value to put in some partition
for ( int p = 0; p < N; p++ )
{
if ( value <= remainder[p] ) // If there is still space in the pth partition
{
remainder[p] -= value;
PART[t] = p;
if ( recurse( N, TEST, t - 1, remainder, PART ) ) return true; // Can we go on with this choice?
else remainder[p] += value; // If not, take it out again
}
}
return false;
}
//======================================================================
bool split( int N, const vector<int> &TEST, vector< vector<int> > &P ) // Divide TEST into N partitions with equal sums
{
int sumT = accumulate( TEST.begin(), TEST.end(), 0 );
if ( sumT % N ) // Fast check that the total actually divides by N
{
cout << "Not divisible by " << N << '\n';
return false;
}
vector<int> PART( TEST.size() ); // Partition that each element of TEST is in
vector<int> remainder( N, sumT / N ); // Remaining margin in each partition
bool ok;
if ( method == BACKTRACK ) ok = backtrack( N, TEST, remainder, PART );
else ok = recurse( N, TEST, TEST.size() - 1, remainder, PART );
// Assemble all partitions from PART into 2-d array P[][]
P.clear();
if ( ok )
{
for ( int t = 0; t < TEST.size(); t++ ) P[ PART[t] ].push_back( TEST[t] );
}
return ok;
}
//======================================================================
int main()
{
srand( time( 0 ) ); // Only needed for random inputs
const int N = 3; // Number of partitions
vector<int> TEST = generateTest(); // Input or generate vector to test
cout << "Original vector: " << TEST << '\n';
vector< vector<int> > P(N);
clock_t start = clock();
bool ok = split( N, TEST, P ); // Partition it (or not)
clock_t end = clock();
if ( ok )
{
cout << "Partitions:\n";
for ( int p = 0; p < N; p++ ) cout << P[p] << '\n';
}
else
{
cout << "Impossible\n";
}
cout << "Time taken = " << 1000.0 * ( end - start ) / CLOCKS_PER_SEC << " ms\n";
}
//======================================================================
|