Pagini recente » Cod sursa (job #29281) | Cod sursa (job #1378950) | Cod sursa (job #1605684) | Cod sursa (job #2961274) | Cod sursa (job #3003590)
/*
Generam toate posibilitatile de flip pentru coloane:
1. Ele sunt siruri de 0 si 1 de lungime m
2. Ele sunt submultimi ale {1, 2, 3, ..., m}
Backtracking => metoda recursiva de a genera lucruri
// 1. Decizii: Pentru fiecare coloana de la 1 la m, o flipuim sau nu?
*/
#include <fstream>
#include <vector>
using namespace std;
vector<int> coloane;
int n, m, a[20][20], sol = -INT_MAX;
ifstream fin("flip.in");
ofstream fout("flip.out");
void flip_col(int col) {
for(int lin = 1; lin <= n; lin++) {
a[lin][col] *= -1;
}
}
void backtracking(int col) {
// Punct de oprire:
if(col == m + 1) {
// In coloane am subsetul curent generat
// Mai intai flipuiesc coloanele:
for(int col : coloane) {
flip_col(col);
}
int total = 0;
for(int lin = 1; lin <= n; lin++) {
int sum = 0;
for(int j = 1; j <= m; j++) {
sum += a[lin][j];
}
total += abs(sum);
}
sol = max(sol, total);
for(int col : coloane) {
flip_col(col);
}
return;
}
//Luam decizia pentru col:
// Decizia 1: nu o adaugam in subset
backtracking(col + 1); // genereaza toate solutiile fara col in subset
// Decizia 2: o adaugam in subset
coloane.push_back(col);
backtracking(col + 1); // genereaza toate solutiile cu col in subset
coloane.pop_back();
}
int main() {
fin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
fin >> a[i][j];
}
}
backtracking(1);
fout << sol << "\n";
return 0;
}