plecakowy problem pomocy !

Question

Witam, czy ma ktoś pomysł jak rozwiązać główną funkcje problemu plecakowego w sposób rekurencyjny bez użycia pętli. Proszę o jakieś wskazówki albo jęśli to możliwe to krótki kod do analizy. Dziękuje i pozdrawiam

Comments

Nie wiem skąd bierzecie takie zadania. Wyciskanie rekurencji tam gdzie nie trzeba, wręcz nie wolno.

---

Pewnie szkoła, studia. Tam zazwyczaj również tłumaczą rekurencje na abstrakcyjnym przykładzie ciągu Fibo ( a każdy kto próbuje tłumaczyć w ten sposób powinien umrzeć ), gdzie dużo prostszym bardziej logicznym przykładem do zrozumienia jest odliczanie np. od 10 do 0. Nigdy nie zrozumiem dlaczego ludzie lubią sobie ( w sumie to bardziej innym ) utrudniać życie.

---

Kwestia systemu edukacji. Zamiast zmienić program i wywalić wszystkich dziadów od informatyki rocznik 60 + specjalizacja Win95, to lepiej było likwidować gimnazja.

Answer 1

Każdą pętle można przerobić na rekurencję, to nie jest chyba za trudnę, czy możesz napisać coś więcej o problemie? Bo w gruncie rzeczy jeżeli chcemy przejść po elementach tablicy od n-tego do zerowego, to funkcja wyglądała by tak:

void rek ( int n. inne_argumenty... )
{
      if ( n == -1 ) return;
      // przetwarzamy n-ty element tablicy
      rek ( n - 1, inne_argumenty... );
}

Bo rozumiem, że mówimy o takim algorytmie dla problemu plecakowego, który dla każdego przedmiotu iteruje się od maksymalnej pojemności do najmniejszej? Wtedy w innych argumentach bedzie wartosc akt przedmiotu, a cala rekurencja bedzie wywolywana w petli przechodzacej po przedmiotach. Jeśli i tej petli chcemy sie pozbyc, to stworzymy kolejna podobna funkcje, gdzie w "//przetwarzamy..." bedzie wywolanie rek dla danego elementu...
 

 

 

Answer 2

Może się przyda :  Rozwiązanie oparte o rekurencje ... po prostu programowanie dynamiczne 

int knapSack(int W, int wt[], int val[], int n)
{
   // Base Case
   if (n == 0 || W == 0)
       return 0;
 
   // If weight of the nth item is more than Knapsack capacity W, then
   // this item cannot be included in the optimal solution
   if (wt[n-1] > W)
       return knapSack(W, wt, val, n-1);
 
   // Return the maximum of two cases: 
   // (1) nth item included 
   // (2) not included
   else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                    knapSack(W, wt, val, n-1)
                  );
}