4736387690

8.    Przypuśćmy, że do problemu wyboru zajęć stosujemy następującą metodę zachłanną. Wybieramy zajęcie o najkrótszym czasie trwania spośród zajęć zgodnych z dotychczasowo wybranymi. Skonstruuj przykład, który dowodzi, że ta strategia nie zawsze prowadzi do optymalnego rozwiązania.

9.    Skonstruuj decyzyjne problemy plecakowe takie, że

(a)    żadna ze strategii zachłannych opisanych na wykładzie nie daje rozwiązania optymalnego,

(b)    każda ze strategii zachłannych opisanych na wykładzie daje rozwiązanie optymalne,

(c)    jedna strategia zachłanna z opisanych na wykładzie daje optymalne rozwiązanie, a pozostałe nie.

7. Dyskretny problem plecakowy

1.    Opracuj metodę dynamiczną rozwiązywania decyzyjnego problemu plecakowego.

Wskazówka. Zmodyfikuj podaną na wykładzie metodę dynamiczną rozwiązywania ogólnego problemu plecakowego.

2.    Złodziej włamał się do mieszkania z torbami, do których może załadować przedmioty o łącznej wadze nie przekraczającej 10 kg. W mieszkaniu znajdują się:

•    2 laptopy o wadze 2 kg. każdy oraz wartości 2000 zł. każdy;

•    sprzęt audio o wadze 3 kg. oraz wartości 2500 zł.;

•    telewizor o wadze 3,5 kg. oraz wartości 1000 zł.;

•    4 antyczne wazy o wadze 1 kg. każda oraz wartości 1500 zł. każda;

•    10 zabytkowych książek o wadze 0,5 kg. każda oraz o wartości 700 zł. każda.

•    DVD o wadze 1,5 kg. oraz wartości 1200 zł.;

Które przedmioty powinien zabrać złodziej, aby wyjść z najcenniejszym łupem.

3.    Pewna firma ma pręty długości 20 m. i chce je sprzedać. Na rynku jest zapotrzebowanie na pręty długości: 9,3,6,13 oraz 15 m. Na jakie