Prezentacja multimedialna

Ciągły problem plecakowy

Jak już wiemy, 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.

Zaprezentowane rozwiązania będziemy testować dla następujących danych:

  • maksymalna pojemność plecaka wynosi 27;

  • możemy pakować części przedmiotów, ale do dyspozycji jest 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

akwarele

blok rysunkowy

cienkopisy

dzienniczek

encyklopedia

flamastry

gumki do mazania

Wartość

3

17

2

1

5

3

4

Waga

9

8

6

6

15

7

2

Już wiesz

Przypomnijmy, w jaki sposób działa algorytm, analizując podane dane.

Zaczniemy od obliczenia ilorazów wartości i wag.

Obliczone ilorazy: 3/9, 17/8, 2/6, 1/6, 5/15, 3/7, 4/2.

Następnie sortujemy je nierosnąco.

Posortowane nierosnąco ilorazy: 17/8, 4/2, 3/7, 3/9, 2/6, 5/15, 1/6.

Daje to następującą kolejność posortowanych nierosnąco przedmiotów: blok rysunkowy, gumki do mazania, flamastry, akwarele, cienkopisy, encyklopedia, dzienniczek (indeksy: 1, 6, 5, 0, 2, 4, 3).

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 blok rysunkowy, którego waga to 8. Jego waga jest mniejsza od pojemności plecaka, zatem możemy spakować ten przedmiot. Pojemność plecaka po spakowaniu tego przedmiotu wynosi 19.

Waga kolejnego przedmiotu (gumek do mazania) wynosi 2, zatem można spakować ten przedmiot. Pojemność plecaka po jego spakowaniu to 17.

Kolejnym przedmiotem są flamastry. Waga tego przedmiotu to 7. Jest mniejsza od pojemności plecaka, zatem zostaje zapakowany. Pozostała pojemność plecaka wynosi 10.

Kolejnym przedmiotem są akwarele, które ważą 9. Mogą zostać spakowane, a pojemność plecaka po ich spakowaniu wynosi 1.

Waga cienkopisów, następnego przedmiotu, wynosi 6. Jest większa od tego, jaka jest pozostała pojemność plecaka, zatem nie można ich 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/6. By obliczyć, jaką wartość ma zapakowana część przedmiotu, uzyskany wynik mnożymy przez wartość całego przedmiotu.

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

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

  • blok rysunkowy: 17

  • gumki do mazania: 4

  • flamastry: 3

  • akwarele: 3

  • cienkopisy: 0,333

Całkowita wartość spakowanych przedmiotów wynosi 27,333. 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

  • wartosci – 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

  • pojemnosc – 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 pojemnosc, 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 pojemnosc; pakujemy po jednej sztuce przedmiotu każdego rodzaju

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

Działanie programu przetestuj dla następujących danych:

Linia 1. String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy znak równości otwórz nawias klamrowy cudzysłów akwarele cudzysłów przecinek cudzysłów blok rysunkowy cudzysłów przecinek. Linia 2. cudzysłów cienkopisy cudzysłów przecinek cudzysłów dzienniczek cudzysłów przecinek. Linia 3. cudzysłów encyklopedia cudzysłów przecinek cudzysłów flamastry cudzysłów przecinek. Linia 4. cudzysłów gumki do mazania cudzysłów zamknij nawias klamrowy średnik. Linia 5. int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci znak równości otwórz nawias klamrowy 3 przecinek 17 przecinek 2 przecinek 1 przecinek 5 przecinek 3 przecinek 4 zamknij nawias klamrowy średnik. Linia 6. int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi znak równości otwórz nawias klamrowy 9 przecinek 8 przecinek 6 przecinek 6 przecinek 15 przecinek 7 przecinek 2 zamknij nawias klamrowy średnik. Linia 7. int n znak równości 7 średnik. Linia 8. int pojemnosc znak równości 27 średnik.

Przykładowe wyniki dla podanych danych:

Linia 1. Spakowano przedmiot blok rysunkowy otwórz nawias okrągły indeks 1 zamknij nawias okrągły. Linia 2. Spakowano przedmiot gumki do mazania otwórz nawias okrągły indeks 6 zamknij nawias okrągły. Linia 3. Spakowano przedmiot flamastry otwórz nawias okrągły indeks 5 zamknij nawias okrągły. Linia 4. Spakowano przedmiot akwarele otwórz nawias okrągły indeks 0 zamknij nawias okrągły. Linia 5. Spakowano 0 kropka 167 przedmiotu cienkopisy otwórz nawias okrągły indeks 2 zamknij nawias okrągły. Linia 7. Wartosc spakowanych przedmiotow dwukropek 27 kropka 333.
R1cIdlP3lIDB6
s
Polecenie 2

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

R1ZDjLXcXvsiW1
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
RCqQVIbcwTPFv
x
Przeczytaj
Sprawdź się