Strona główna » Algorytmy » Artykuły » Podział Pręta
 

Podział Pręta

https://mattomatti.com/a0129

Zadanie

Dany jest pręt o pewnej długości oraz tablica wartości ile jest wart jak długi pręt. Podziel pręt na takie kawałki, aby uzyskać jak największą wartość. Rozwiąż zadanie używając dwóch różnych metod pisania programu. Sprawdź działanie napisanego programu.

Przykład

Dany jest pręt o długości 5 oraz następująca tabelka wartości:

Długość12345
Wartość22765

Początkowo pręt przed podziałem jest wart 5. Początkowo może wydawać się, że należy pręt rozdzielić na 5 elementów: {1, 1, 1, 1, 1} co daje wynik 10. Jednak okazuje się, że jeśli zostanie podzielona na kawałki {3, 1, 1} to uzyskany zostanie wynik 11.

Implementacja

Założenia

Program nie sprawdza poprawności danych wejściowych. Użytkownik dane podaje w następującej kolejności: pierwsza liczba n określa długość pręta, a następna k ile cennik ma pozycji. Następnie podawane jest k liczb całokowitych, gdzie i-ta wartość oznacza sprzedaż pręta o długości i (indeksujemy od 1).

Przykładowo jeśli mamy pręt o długości n = 10, a cennik składa się z k = 5 pozycji kolejno {3, 2, 1, 5, 4} to zostanie to przekazane jako:

  1. 10
  2. 5
  3. 3 2 1 5 4

Rekurencja

Jedną z metod jaką można rozwiązać to zadanie polega na rekurencyjnym skracaniu pręta tak, aby sprawdzić wszystkie możliwe kombinacje. Nie jest to jednak najbardziej optymalna metoda, ponieważ wiele obliczeń zostanie wykonane kilka razy. Pozostają jednak przy rekurencji kod źródłowy programu wygląda następująco:

  1. int przytnijPret(int n, int* cennik, int k) {
  2.   if (n <= 0)
  3.     return 0;
  4.   int maks = INT_MIN;
  5.   for (int i = n < k ? n : k; i > 0; i--) {
  6.     int sprz = cennik[i - 1] + przytnijPret(n - i, cennik, i);
  7.     if (sprz > maks)
  8.       maks = sprz;
  9.   }
  10.   return maks;
  11. }

Warunkiem zakończenia rekurencji jest (2.) wykrycie, że nie ma już pręta do podziału i wtedy należy (3.) zwrócić 0. W przeciwnym razie (4.) ustal początkowo maksimum dalszych cięć na minimalną wartość typu i (5.) dla każdego możliwego podziału: (6.) podziel i odczytaj zwrócony wynik. Jeśli (7.) jest większy od aktualnego maksimum to: (8.) zaktualizuj maksimum. Na koniec (10.) zwróć obliczoną wartość maksymalną.

Testowanie funkcji

W celu przetestowania kodu można zastosować poniższy kod, który wczyta odpowiednie dane, a następnei wyświetli wynik:

  1. int main () {
  2.   int n, k;
  3.   cout << "Podaj dlugosc preta\n n = ";
  4.   cin >> n;
  5.   cout << "Ile pozycji ma cennik?\n k = ";
  6.   cin >> k;
  7.   cout << "Podaj cennik:\n";
  8.   int* cennik = new int[k];
  9.   for (int i = 0; i < k; i++)
  10.     cin >> cennik[i];
  11.   cout << przytnijPret(n, cennik, k);
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz funkcję przytnijPret(), która wypisze użytkownikowi jak należy podzielić pręt, aby uzyskać jak największą wartość. Funkcja powinna wypisać jako pierwszą liczbę łączną wartość podzielonych fragmentów, a następnie podać wszystkie długości fragmentów prętów. Przykładowo dla danych:

  1. 10
  2. 5
  3. 3 2 1 5 4

Program powinien wypisać:

  1. 30 | 1 1 1 1 1 1 1 1 1 1