Löysin tällaisen ongelma, jolle ei ollut annettu vastausta. Kun en kerran matemaattista ratkaisua keksinyt, etsin lähinnä mahdollisimman nopeaa algoritmia tehtävälle.
Ongelma: A on nxn-matriisi, jonka alkiot ovat {1,2,...,n^2} jossain järjestyksessä. Olkoon r_i A:n i:nnen rivin alkioiden tulo ja c_i A:n i:nnen sarakkeen alkioiden tulo. Olkoon d_1 lävistäjäalkioiden A_{i,i} tulo ja d_2 toisten lävistäjäalkioiden A_{i,n-i+1} tulo. Miten alkiot on sijoitettu matriisiin, kun summa (c_i+r_i,i=1,...,n)+d_1+d_2 on maksimaalinen?
Hmm. Taisin löytää ratkaisun. Simuloitu jäähdytys näyttäisi toimivan tähän ongelmaan. Vielä kun osaisi ohjelmoida sen!
Jos ymmärsin ongelman oikein, ratkaisu on hyvin yksinkertainen:
Kaikkien c_i:den summa on yhtä kuin kaikkien matriisin alkioiden summa, samoin kaikkien r_i:den summa. Siispä ainoastaan kahden viimeisen termin, d_1 ja d_2, suuruuteen voi vaikuttaa sijoittelulla.
Jos n on pariton, aseta suurin alkio keskelle ja seuraavat 2*(n-1) suurinta alkiota lävistäjille. Lopuksi täytä tyhjät ruudut lopuilla alkioilla.
Jos n on parillinen, aseta 2n suurinta alkiota lävistäjille ja loput ei-lävistäjille.
apinamies, kyse oli tuloista eikä summista, joten tuo ei toimi.
Ah, niinpä olikin. Ihmettelinkin, kun ei kukaan muu ollut vaivautunut vastaamaan :D
Aihe on jo aika vanha, joten et voi enää vastata siihen.