Prezentacja multimedialna

Ciągły problem plecakowy

Ciągły problem plecakowy to taki wariant problemu plecakowego, w którym możemy pakować do plecaka fragmenty (części) przedmiotów.

W tej sekcji przedstawimy, w jaki sposób rozwiązać ciągły problem plecakowy, wykorzystując algorytm zachłanny.

Przykład 1

Zapoznajmy się z tym, jaki sposób działa algorytm, analizując podane dane:

  • maksymalna pojemność plecaka wynosi 37;

  • możemy pakować części przedmiotów, ale do dyspozycji jest tylko po jednej sztuce przedmiotu każdego rodzaju;

  • przedmioty, które mamy do dyspozycji, mają następujące wartości oraz wagi:

Przedmiot – i

0

1

2

3

4

5

6

Nazwa

akwamaryn

beryl

chalcedon

diament

eudialit

fluoryt

granat

Wartość

12

18

6

9

7

3

5

Waga

5

9

12

4

21

7

6

Zaczniemy od obliczenia ilorazów wartości i wag. W przypadku zaprezentowanego przykładu te ilorazy to: 12/5, 9/4, 18/9, 5/6, 6/12, 3/7, 7/21.

Daje to następującą kolejność posortowanych nierosnąco przedmiotów: akwamaryn, diament, beryl, granat, chalcedon, fluoryt, eudialit (indeksy: 0, 3, 1, 6, 2, 5, 4).

Dla każdego posortowanego przedmiotu sprawdzamy, czy można go spakować w całości, a jeśli nie, to w jakiej części.

Wybieramy pierwszy przedmiot. To akwamaryn, którego waga to 5. Jego waga jest mniejsza od pojemności plecaka, zatem możemy spakować ten przedmiot. Pojemność plecaka po spakowaniu tego przedmiotu wynosi 32.

Waga kolejnego przedmiotu (diamentu) wynosi 4, zatem można spakować ten przedmiot. Pojemność plecaka po jego spakowaniu to 28.

Kolejnym przedmiotem jest beryl. Waga tego przedmiotu to 9. Jest mniejsza od pojemności plecaka, zatem zostaje zapakowany. Pozostała pojemność plecaka wynosi 19.

Kolejnym przedmiotem jest granat, który waży 6. Może zostać zapakowany, a pojemność plecaka po jego zapakowaniu wynosi 13.

Następny przedmiot, chalcedon, waży 12. Waga jest mniejsza od pojemności plecaka, zatem chalcedon może zostać zapakowany w całości. Pozostała pojemność plecaka to 1.

Waga fluorytu, następnego przedmiotu, wynosi 7. Jest większa od tego, jaka jest pozostała pojemność plecaka, zatem nie można go spakować w całości.

Należy zatem obliczyć, jaką część można spakować. By to zrobić, dzielimy pozostałą pojemność plecaka przez wagę przedmiotu. Wynik to 1/7. By obliczyć, jaką wartość ma zapakowana część przedmiotu, uzyskany wynik mnożymy przez wartość całego przedmiotu.

Uzyskana wartość to 3 × 1/7, co daje 3/7. Po zaokrągleniu do trzeciego miejsca po przecinku wynik wynosi 0,429.

Wypełniliśmy tym samym całe miejsce w plecaku.

Obliczmy całkowitą wartość spakowanych przedmiotów:

  • akwamaryn: 12

  • diament: 9

  • beryl: 18

  • granat: 5

  • chalcedon: 6

  • fluoryt: 0,429

Całkowita wartość spakowanych przedmiotów wynosi 50,429. Wykorzystaliśmy całe miejsce.

Polecenie 1

Zapisz program, który rozwiąże ciągły problem plecakowy. Do dyspozycji masz po jednej sztuce każdego przedmiotu.

Wynik zaokrąglij do trzech miejsc po przecinku.

Specyfikacja problemu:

Dane:

  • nazwy – tablica łańcuchów znaków; nazwy poszczególnych przedmiotów

  • wartości – tablica liczb naturalnych; wartości poszczególnych przedmiotów

  • wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów

  • n – liczba naturalna; liczba rodzajów przedmiotów

  • pojemność – liczba naturalna; maksymalna pojemność plecaka

Wynik:

  • spakowane przedmioty (w całości lub części), których całkowita waga nie przekracza wartości przechowywanej w zmiennej pojemność, a których całkowita wartość jest największa wśród możliwych wypełnień plecaka rzeczami o takiej wadze, która nie przekracza wartości zmiennej pojemność; pakujemy po jednej sztuce przedmiotu każdego rodzaju

  • całkowita wartość spakowanego plecaka zaokrąglona do trzech miejsc po przecinku

Linia 1. funkcja sortuj otwórz nawias okrągły wartość podkreślnik do podkreślnik wagi przecinek indeksy przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka n minus 2 przecinek. Linia 3. dla każdego j znak równości 0 przecinek 1 przecinek 2 przecinek kropka kropka kropka n minus i minus 2. Linia 4. jeżeli wartość podkreślnik do podkreślnik wagi otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny wartość podkreślnik do podkreślnik wagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy. Linia 5. pomocnicza podkreślnik wdw ← wartość podkreślnik do podkreślnik wagi otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 6. wartość podkreślnik do podkreślnik wagi otwórz nawias kwadratowy j zamknij nawias kwadratowy ← wartość podkreślnik do podkreślnik wagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy. Linia 7. wartość podkreślnik do podkreślnik wagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy ← pomocnicza podkreślnik wdw. Linia 9. pomocnicza podkreślnik indeksy ← indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 10. indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy ← indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy. Linia 11. indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy ← pomocnicza podkreślnik indeksy. Linia 13. funkcja ciągłyPlecak otwórz nawias okrągły nazwy przecinek wartości przecinek wagi przecinek n przecinek pojemność zamknij nawias okrągły. Linia 15. kratka Uzupełnij kod. Linia 17. nazwy ← cudzysłów akwamaryn cudzysłów przecinek cudzysłów beryl cudzysłów przecinek cudzysłów chalcedon cudzysłów przecinek. Linia 18. cudzysłów diament cudzysłów przecinek cudzysłów eudialit cudzysłów przecinek cudzysłów fluoryt cudzysłów przecinek cudzysłów granat cudzysłów. Linia 19. wartości ← 12 przecinek 18 przecinek 6 przecinek 9 przecinek 7 przecinek 3 przecinek 5. Linia 20. wagi ← 5 przecinek 9 przecinek 12 przecinek 4 przecinek 21 przecinek 7 przecinek 6. Linia 21. n ← 7. Linia 22. pojemność ← 37. Linia 24. ciągłyPlecak otwórz nawias okrągły nazwy przecinek wartości przecinek wagi przecinek n przecinek pojemność zamknij nawias okrągły.
Ważne!

W rozwiązaniu wykorzystujemy funkcję zaokr_do_trzech_miejsc, której zadaniem jest zaokrąglenie przekazanego do niej argumentu do trzech miejsc po przecinku.

Polecenie 2

Zapoznaj się z prezentacją przedstawiającą rozwiązanie ciągłego problemu plecakowego.

RMNdU9sokq82g1
Prezentacja alternatywna znajduje się w trybie dostępności.
Prezentacja multimedialna przedstawiająca rozwiązanie ciągłego problemu plecakowego
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.
Polecenie 3
RnArzvwuEJ86t
c
Polecenie 4
R8PLKkjkF7VuO
c
Przeczytaj
Sprawdź się