Problema (urgent)

[•Neamtzu]

Am urmatoarea problema:

Am o matrice N * N cu elemente numere naturale.

Vreau sa parcurg aceasta matrice de la linia 1 la linia N (alegand cate un element de pe fiecare linie) cu conditia ca odata trecut printr-un element, restul elementelor de pe aceeasi coloana nu mai pot fi parcurse pana la sfarsit. Vreau sa scot o secventa de suma maxima prin acest tip de parcurgere.

Am nevoie de o idee de rezolvare destul de urgent

[•Cosmin]

Pai de ce e asa urgent?

[•Neamtzu]

As prefera o idee decat un raspuns off-topic

[•MciprianM]

Daca e urgent urgent sa fie! Poti sa incerci backtracking (generezi permutari). Vezi http://en.wikipedia.org/wiki/Rook_polynomial

[•Neamtzu]

Backtracking e mult prea lent, N <= 400

[•Mishu91]

Dintr-un element poti merge doar intr-un element adiacent sau in oricare altul?

[•klamathix]

Un cuplaj de cardinalitate N si cost maxim ?

[•Neamtzu]

@Andrei
Dintr-un element poti merge in oricare altul pe a carui coloana nu ai mai fost inainte (trebuie ales un element de pe fiecare coloana)

@Mihai
Din cate imi dau seama asa e, ce solutie imi propui? Presupun ca folosesc flux maxim unde reteaua are S care duce in N noduri cu capacitatea infinit, apoi cele N noduri duc in alte N noduri (toate combinatiile posibile) cu capacitatile date de matricea mea si apoi alea duc in T (tot cu capacitatea infinit).

[•Mishu91]

Nu, din S vei avea muchii în N noduri de capacitate 1 și cost 0, din nodul din dreapta i și nodul din stânga j vei avea capacitate 1 și cost -A[ i ][ j ], iar din cele N noduri din dreapta vei avea muchii de capacitate 1 și cost 0 către destinație. Iar apoi dai bătaie cu cuplaj maxim de cost minim. Suma cerută va fi -costul cuplajului.

[•klamathix]

Nu. E cum a spus Andrei Misarca. Exista si o solutie care nu implica flux , se numeste algoritmul ungar din cate tin minte.

Look:
http://infoarena.ro/problema/cmcm

[•BitOne]

Poate nu inteleg problema, dar tu trebuie sa alegi un element de pe fiecare coloana a.i suma sa fie maxima, da ?
Atunci de ce nu alegi maximul de pe fiecare coloana si gata, sau imi scapa mie un detaliu ? 

[•Mishu91]

Și dacă maximele de pe fiecare coloană sunt pe aceeași linie ce faci?

[•BitOne]

Și dacă maximele de pe fiecare coloană sunt pe aceeași linie ce faci?

A, deci acest detaliu imi scapa , thanks

[•Neamtzu]

Ms de raspunsuri, works wonderfully