Algorytm zachłanny-jak zaimplementować?

0

Szympans je banany. Zjedzenie jednego owocu zajmuje mu minutę (je po jednym na raz).
Wiadomo, że każdy z bananów psuje się po pewnym czasie, a szympans chce spożyć jak najwięcej
świeżych bananów – zepsutych nie rusza. Zaproponuj możliwie efektywny algorytm, który mając
zadane n bananów (1<=n<=1000000), z których i-ty owoc psuje się po bi minutach (1<=bi<=1000),
wyznaczy optymalną kolejność jedzenia świeżych bananów, przy której szympans najbardziej się
naje. W przypadku istnienia kilku optymalnych kolejności, algorytm może podać dowolne z nich.

Dla przykładowych danych:
1, 5, 4, 1, 3 //czasy ważności (w minutach) pięciu bananów (numeracja od 1 do 5)
Wynikiem są cztery kolejno jedzone banany o numerach:
1 3 5 2 //nie jest możliwe, by szympans zjadł wszystkie 5 bananów

Wiem, że algorytm za każdym razem ma wybierać banan, którego data ważności jest najkrótsza. Tylko złożoność mi wychodzi pseudowielomianowa.

Pseudokod:

int banany[]={1,5,4,1,3};
while(min!=0){
    for(i=0;i<banany.length;i++){
        if(banany[i]<min){
             min=banany[i]; //znalezienie banana z najkrótszą ważnością
             index=i;         zapamiętanie indeksu banana
}
       banany[i]--; // upływa czas gdy szympans je banana przez 1 minutę
}
        banany[index]=0;  // wykasowanie banana zjedzonego przez "zrobienie" go zepsutym
        dodaj_do_wyniku (index);
}

co o tym sądzicie?
Proszę o wyrozumiałość, jeśli głupotę napisałem

0

Jak posortujesz dane wejściowe, to później jest znacznie łatwiej,

int[] banany = { 1, 5, 4, 1, 3 };

List<Banan> bannany2 = new List<Banan>(banany.Length);
for (int i = 0; i < banany.Count(); ++i)
    bannany2.Add(new Banan() { index = i + 1, termin = banany[i] });

bannany2 = bannany2.OrderBy(x => x.termin).ToList();

List<int> rozwiazanie = new List<int>();

int j = 0;
foreach (Banan banan in bannany2)
{
    if (banan.termin > j)
    {
        rozwiazanie.Add(banan.index);
        j++;
    }
} 

class Banan
{
    public int index;
    public int termin;
} 
0

Można w O(n), w pythonie:

def chimpanzee_planner(bananas_life_time):
    planner = [-1] * 1001

    for i, t in enumerate(bananas_life_time):
        planner[t] = i + 1

    return [i for i in planner if i != -1]


print(chimpanzee_planner([1, 5, 4, 1, 3]))
print(chimpanzee_planner([1, 1, 1]))
print(chimpanzee_planner([1, 2, 3, 4, 5]))
print(chimpanzee_planner([5, 4, 2, 3, 1]))

Korzystamy z faktu, że czas życia banana jest raczej mały i możemy sobie spokojnie zarezerwować 1001 elementów (bo indeksowanie od 1).
Później tylko patrzymy w kolejności od 1 do 1000, czy jest jakiś banan (indeks) do zjedzenia.

Łatwo to zmodyfikować, tak by dla danego czasu trzymać listy indeksów bananów i produkować wszystkie możliwe rozwiązania, czy liczyć ilość rozwiązań.

2
yarel napisał(a):

Można w O(n), w pythonie:

def chimpanzee_planner(bananas_life_time):
    planner = [-1] * 1001

    for i, t in enumerate(bananas_life_time):
        planner[t] = i + 1

    return [i for i in planner if i != -1]


print(chimpanzee_planner([1, 5, 4, 1, 3]))
print(chimpanzee_planner([1, 1, 1]))
print(chimpanzee_planner([1, 2, 3, 4, 5]))
print(chimpanzee_planner([5, 4, 2, 3, 1]))

Korzystamy z faktu, że czas życia banana jest raczej mały i możemy sobie spokojnie zarezerwować 1001 elementów (bo indeksowanie od 1).
Później tylko patrzymy w kolejności od 1 do 1000, czy jest jakiś banan (indeks) do zjedzenia.

Łatwo to zmodyfikować, tak by dla danego czasu trzymać listy indeksów bananów i produkować wszystkie możliwe rozwiązania, czy liczyć ilość rozwiązań.

Dla np. chimpanzee_planner([3,1,3]) dostaniesz wynik [2, 3] choć szympans mógłby spokojnie zjeść wszystkie banany ;)

Np. [2, 1, 3] byłoby jak najbardziej poprawnym wynikiem.

Trochę gorzej, bo wymaga sortowania, ale powinieneś otrzymać prawidłowy wynik:

from typing import List

def chimpanzee_planner(bananas_lifetimes: List[int]) -> List[int]:
  to_eat_list: List[int] = []
  sorted_lifetimes = [(idx, lifetime) for idx, lifetime in enumerate(bananas_lifetimes)]
  sorted_lifetimes.sort(key = lambda el: el[1])
  for idx, lifetime in sorted_lifetimes:
    if lifetime > len(to_eat_list):
      # indeksowanie od 1
      to_eat_list.append(idx + 1)
  return to_eat_list

dla chimpanzee_planner([3, 1, 3]) dostajesz poprawny output: [2, 1, 3] :)

0

@yarel masz rację, da się to zrobić. Chociaż nie dam głowy, czy nie popełniłem tym razem O(n^2), choć podobno append i get w listach Pythona ma O(1)

Tylko kod robi się zagmatwany:

from typing import List, Tuple
 
def chimpanzee_planner(bananas_lifetimes: List[int]) -> List[int]:
  to_eat_list: List[int] = []
  list_of_lists: List[List[Tuple]] = [[] for _ in range(max(bananas_lifetimes))]
  indexed_lifetimes: List[Tuple] = [(idx, lifetime) for idx, lifetime in enumerate(bananas_lifetimes)]
  # Tu na dobrą sprawę przydałoby się jakieś group_by po długości życia
  for idx, lifetime in indexed_lifetimes:
    list_of_lists[lifetime - 1].append((idx, lifetime))
  indexed_lifetimes = [(idx, lifetime) for sublist in list_of_lists for idx, lifetime in sublist]
  for idx, lifetime_tuple in enumerate(indexed_lifetimes):
    if lifetime_tuple[1] > len(to_eat_list):
      # indeksowanie od 1
      to_eat_list.append(lifetime_tuple[0]+ 1)
  return to_eat_list

1 użytkowników online, w tym zalogowanych: 0, gości: 1