Cálculo práctico de combinatoria con repeticiones, bitset

/* Autor: Carlos D. Alvarez Fecha: 16- 09 - 2016 */ #include <iostream> #include <string> #include <iomanip> #include <vector> #include <cstdlib> #include <cstdio> #include <bitset> using namespace std; class Combinacion { private: int Tiempo; bitset<26> Posiciones; public: Combinacion(): Tiempo(0){} void SetPos(bitset<26> Pos) { Posiciones = Pos; } void Imprimir(int N) { for (int i = 0; i < N; i++) { cout << Posiciones[i] << " "; } } int GetTiempo(vector<int> Lienzos, int K) { Tiempo = 0; int *Tiempos = new int[Lienzos.size()]; memset(Tiempos,0, sizeof(int)* (Lienzos.size())); int Pm = -1; for (int i = 0; i < Lienzos.size(); i++) { if (Posiciones[i]) Pm++; Tiempos[Pm] += Lienzos[i]; } for (int i = 0; i < Lienzos.size()-1; i++) { if (Tiempos[i] > Tiempo) { Tiempo = Tiempos[i]; } } delete[] Tiempos; return Tiempo; } }; int main (int CantidadParam, char** Params) { /* SIENDO H, EL NUMERO DE INSTANCIAS N, EL NUMERO DE MAGNITUDES (LIENZOS), K, EL NUMERO DE DIVISIONES (PINTORES) Y M, EL VALOR DE LAS MAGNITUDES (TAMAÑOS) QUE VAN DESDE M(0) A M(N-1) ENTONCES, SIENDO 25 LA CANTIDAD MÁXIMA DE LIENZOS. TENEMOS 42050 POSIBILIDADES DIFERENTES. */ int I, N, K; vector<int> M; // Se lee I, N y K cin >> I; for (int p = 0; p < I; p++) { cout << "Instancia " << p+1 << "... Ingrese N, K y M\n"; cin >> N; if (N < 1 || N > 25) { return 1; } cin >> K; if (K < 1 || K > N) { return 1; } fflush(stdin); M.resize(N); // Se leen las dimensiones for (int i = 0; i < N; i++) { string temp; cin >> temp; M[i] = atoi(temp.c_str()); } if (K == N) { int mayor = 0; for (int i = 0; i < N; i++) { if (M[i] > mayor) { mayor = M[i]; } } cout << endl << "Tiempo mínimo necesario: " << mayor; fflush(stdin); cin.get(); continue; } if (K == 1) { int suma = 0; for (int i = 0; i < N; i++) { suma += M[i]; } cout << endl << "Tiempo minimo necesario: " << suma; fflush(stdin); cin.get(); continue; } // Hallamos las combinaciones posibles vector <Combinacion> Combinaciones; bitset<26> Comb; for (int i = 0; i < N; i++) { Comb[i] = 1; } unsigned int CombinacionesTotales = Comb.to_ulong(); Comb.reset(); unsigned int CombinacionesEncontradas = 0; int PinturasMaximas = N-K+1; if (N > 20) { cout << "\nPara N mayor a 20, el tiempo de espera puede ser considerable\n" << "Esto dependera de la capacidad de su maquina. Por favor sea paciente.\n"; } for (int i = 0;; i++) { Comb = i; // Numero de pintores en el bitset int NP = 0; for (int j = 0; j < N; j++) { NP += Comb[j]; } if (NP == K && Comb[0]) { Combinaciones.resize(++CombinacionesEncontradas); Combinaciones[CombinacionesEncontradas-1].SetPos(Comb); } if (Comb[N]) { break; } } // Luego de todos los cálculos, leemos el tiempo menor int TiempoMenor = 0; Combinacion Optima; for (int i = 0; i < N; i++) { TiempoMenor += M[i]; } for (int i = 0; i < Combinaciones.size()-1 ; i++) { int tt = Combinaciones[i].GetTiempo(M, K); if (tt < TiempoMenor) { TiempoMenor = tt; Optima = Combinaciones[i]; } } // Y mostramos el resultado en pantalla... cout << endl << "COMBINACIONES TOTALES: " << CombinacionesTotales << endl << "COMBINACIONES POSIBLES: " << CombinacionesEncontradas << endl << "Tiempo menor encontrado: " << TiempoMenor << endl << "Combinacion: "; Optima.Imprimir(N); // Y ya... (Fuaaaaaaah!!!) cin.get(); cin.get(); fflush(stdin); cout << endl << endl; } return 0; }