CSES - Tehtävät

Repunpakkaus

Kehitä 2-approksimaatioalgoritmi seuraavaan ongelmaan:

Sinulle annetaan repun maksimipaino uu sekä nn esinettä, joista ii:nnellä on paino wiw_i ja arvo cic_i. Valitse joukko esineitä, jotka maksimoivat arvojen summan niin ettei niiden yhteispaino ylitä repun maksimipainoa.

Solmupeite

  1. Toteuta lineaarinen ohjelma (painottomaan) solmupeiteongelmaan Pythonin MIP-paketilla.

  2. Ohjelma voi tuottaa ratkaisun, jossa osan muuttujista arvo ei ole kokonaisluku. Solmupeitteessä solmut joko sisältyvät peitteeseen (1) tai eivät sisälly (0). Tarkastele mitä käy, jos pyöristät ratkaisun, eli valitset solmupeitteeseen kaikki solmut, joiden arvo on vähintään 0.50.5:

a) Vakuuta itsellesi, että ratkaisu tuottaa solmupeitteen.

b) Kuinka hyvän approksimaation se tuottaa? (Osoita ensin, että lineaariohjelma tuottaa alaraja ja pyöristys ylärajan)

Kauppamatkustajan ongelma

Kehitä 2-approksimaatioalgoritmi seuraavaan ongelmaan:

Sinulle annetaan nn kaupungin koordinaatit (xi,yi)(x_i, y_i). Etsi lyhin polku, joka käy kaikissa kaupungeissa, kun kahden kaupungin etäisyys määritellään niiden euklidinen etäisyytenä, eli d(i,j)=(xixj)2+(yiyj)2d(i, j) = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}.