Kaada pllk:n väitöskirja!

Annettuna on lukumatriisi, jossa on n riviä ja m saraketta. Lisäksi on annettuna n väliä [a₁,b₁], [a₂,b₂], ..., [a_n,b_n].

Tehtäväsi on valita jokaiselta riviltä väli niin, että rivin i välin pituus on välillä [a_i,b_i]. Lisäksi rivin i+1 välin tulee alkaa aina yksi sarake rivin i välin päättymisen jälkeen.

Ratkaisun hyvyys on minimi kaikkien välien summista, ja tehtäväsi on etsiä paras ratkaisu.

Väitöskirja esittää monimutkaisen algoritmin, jonka aikavaativuus on O(nm), kun matriisin kaikki luvut ovat epänegatiivisia.

Mahdollisia tapoja kaataa väitöskirja:

• keksi yksinkertainen algoritmi tehtävään
• keksi O(nm)-algoritmi, joka toimii myös negatiivisilla luvuilla