Algorytmy zachłanne

Ciągły problem plecakowy

Jest N towarów. Każdego jest w_i kilogramów, a jeden kilogram kosztuje c_i. Możemy unieść maksymaknie K kilkogramów. Ile którego towaru wziąć, aby łączna wartość zabranych towarów była jak największa?

Przedziały

Danych jest N przedziałów: [a_i, b_i]. Chcemy przypisać liczby od 1 do N przedziałom (każdą innemu przedziałowi) tak, aby liczba leżała w przypisanym jej przedziale lub stwierdzić, że się nie da.

Trójramienny dźwig

Obok siebie stoi w rzędzie N skrzynek. Mamy do dyspozycji dźwig, który podnosi na raz trzy skrzynki (zawsze muszą być trzy). Odległości między podnoszonymi skrzynkami są stałe i wynoszą a i b. Dźwig może więc podnosić skrzynki numer n, n+a, n+a+b lub numer n, n+b, n+a+b (dla dowolnego n). W jaki sposób przenieść wszystkie skrzynki i czy w ogóle się da?

Ułamki proste

Dany jest ułamek a/b (gdzie 0<a<b). Chcemy go przedstawić jako sumę ułamków prostych (czyli postaci 1/n) o różnych mianownikach.