Zadanie C++ plecak metoda zachłanna

[Roundstic 0]

Polecenie brzmi:

 

Zaprojektuj i zaimplementuj zachłanny algorytm pakowania plecaka. Dany jest plecak o pojemności 0 <= W <= 10000 oraz 0 <= n <= 10000 przedmiotów o wagach 1 <= w <= 10000 oraz wartościach 0 <= c <= 1000. Program ma wypisywać wartość zapakowanego plecaka.

 

Nie wiem, czy mój kod jest dobry, coś wylicza, ale czy najlepszą opcje to nie wiem

 

 

 

 

 

#include <iostream>
using namespace std;

int main()
{
   int n;// przedmiotów
   double W; // pojemność plecaka/ waga
   double wartosc = 0;// wartosc plecaka przedmiotow w plecaku
   int sztuk = 0; // liczba sztuk która jest w plecaku
   cout<<" Podaj liczbę przedmiotów: ";
   cin>>n;

   cout<<" Podaj pojemność plecaka: ";
   cin>>W;

   cout<<"Wpisz wartosci przedmiotow: ";
   double p_wart[1000];// wartość przedmiotu;
   for(int i = 0; i < n; i++)// kolejne liczby do tablicy
   {
       cin>>p_wart[i];
   }

   cout<<"Wpisz ile zajmują te przedmioty: ";
   double p_waga[10000];
   for(int i=0; i<n; i++) // kolejne elementy do tablicy
   {
       cin>>p_waga[i];
   }

   for(int i=0; i<n; i++)
   {
       sztuk = W / p_waga[i];
       W = W - sztuk*p_waga[i];
       wartosc = wartosc + sztuk * p_wart[i];

   }

   cout<<wartosc;
   return 0;
}

[Roundstic 0]

Wprowadziłem dodatkowo sortowanie, bo mam w zeszycie napisane, że możemy wybrać jedną z 2 opcji w tym zadaniu:

 

1. Pakowanie najcenniejszych. Lub

2. Pakowanie najmniejszych

 

tylko mam teraz problem, bo sortuje się jedynie wartość i przy tym gubi się odpowiednia waga przedmiotu

include <iostream>
using namespace std;
int ZnajdzMaksimum(double T[], int L, int P)
{
   int indeks = L;
   for (int i= L +1; i<=P; i++)
   {
       if(T[indeks]<T[i])
       {
           indeks = i;
       }
   }
   return indeks;
}


//****************************************************

void sortuj(double T[], int n)
{
   int i;
   for(i=0; i<n; i++)
   {
       int indeks = ZnajdzMaksimum(T, i, n-1);
       swap(T[i], T[indeks]);
   }
}


int main()
{
   int n;// przedmiotów
   double W; // pojemność plecaka/ waga
   double wartosc = 0;// wartosc plecaka przedmiotow w plecaku
   int sztuk = 0; // liczba sztuk która jest w plecaku

   cout<<" Podaj liczbę przedmiotów: ";
   cin>>n;

   cout<<" Podaj pojemność plecaka: ";
   cin>>W;

   cout<<"Wpisz wartosci przedmiotow: ";
   double p_wart[1000];// wartość przedmiotu;
   for(int i = 0; i < n; i++)// kolejne liczby do tablicy
   {
       cin>>p_wart[i];
   }
   sortuj(p_wart, n);
   cout<<"Wpisz ile zajmują te przedmioty: ";
   double p_waga[10000];
   for(int i=0; i<n; i++) // kolejne elementy do tablicy
   {
       cin>>p_waga[i];
   }

   for(int i=0; i<n; i++)
   {

       sztuk = W / p_waga[i];
       W = W - sztuk*p_waga[i];
       wartosc = wartosc + sztuk * p_wart[i];

   }

   cout<<wartosc;
   return 0;
}

Edytowane 20 Listopada 2019 przez Roundstic

[Bono[UG] 1625]

Masz złe rozmiary tablic. Przedmiotów może być 10000, tymczasem tablicę na wartości przedmiotów dałeś o rozmiarze 1000 (pomyliłeś z ich maksymalną wartością?).

 

Sprawdź zgodność opisu zmiennej sztuk z jej faktycznym wykorzystaniem.

W pętli upychającej do plecaka nie masz żadnego warunku sprawdzającego, czy jego pojemność nie została przekroczona.

Dobrze jakbyś opisał co miałeś na myśli, jak ten algorytm miał działać.

 

 

Odnośnie sortowania. Skoro masz dwie tablice przechowujące wartości związane z jednym przedmiotem, to przy sortowaniu musisz zamienić miejscami elementy w obu tablicach.

W tym zadaniu najprościej dodać argument do funkcji sortującej, przyjmujący drugą tablicę. Np.

void sortuj(double first[], double second[], int n)
{
   int i;
   for(i=0; i<n; i++)
   {
       int indeks = ZnajdzMaksimum(first, i, n-1);
       swap(first[i], first[indeks]);
       swap(second[i], second[indeks]);
   }
}

Wtedy żeby posortować po wadze lub wartości, trzeba podać tablice we właściwej kolejności. W tym przykładzie pierwsza tablica ma porównywane wartości.

sortuj(waga, wartosci, n) - posortuje po wadze przedmiotów obie tablice

sortuj(wartosci, waga, n) - posortuje po wartościach przedmiotów obie tablice

 

Edit: skoro jest pakowanie najmniejszych, to sprawdź czy masz we właściwym kierunku posortowane dane.

 

Docelowo warto zainteresować się strukturami, a jeszcze lepiej obiektami oraz jak do funkcji sortującej przekazać operator porównania jako argument.

Finalnie kontenery i std::algorithm.

 

 

Odnośnie najlepszej opcji, to rozwiń myśl czy chodzi o samo zakodowanie, czy o to czy algorytm znajduje optymalne rozwiązanie.

W drugim przypadku odpowiedź dla algorytmów zachłannych jest prosta - raczej nie, czyli najczęściej znajduje suboptymalne ale może się trafić najlepsze.

Edytowane 21 Listopada 2019 przez Bono[UG]

[Roundstic 0]

Mam tak, jak chciałem w pętli dodać drugą pętlę while(W>=0) to już nie działało

 

 

#include <iostream>
using namespace std;
int ZnajdzMaksimum(double T[], int L, int P)
{
   int indeks = L;
   for (int i= L +1; i<=P; i++)
   {
       if(T[indeks]<T[i])
       {
           indeks = i;
       }
   }
   return indeks;
}


//****************************************************

void sortuj(double first[], double second[], int n)
{
   int i;
   for(i=0; i<n; i++)
   {
       int indeks = ZnajdzMaksimum(first, i, n-1);
       swap(first[i], first[indeks]);
       swap(second[i], second[indeks]);

   }
}


int main()
{
   int n;// przedmiotów
   double W; // pojemność plecaka/ waga
   double wartosc = 0;// wartosc plecaka przedmiotow w plecaku
   int sztuk = 0; // liczba sztuk która jest w plecaku

   cout<<" Podaj liczbę przedmiotów: ";
   cin>>n;

   cout<<" Podaj pojemność plecaka: ";
   cin>>W;

   cout<<"Wpisz wartosci przedmiotow: ";
   double p_wart[1000];// wartość przedmiotu;
   for(int i = 0; i < n; i++)// kolejne liczby do tablicy
   {
       cin>>p_wart[i];
   }

   cout<<"Wpisz ile zajmują te przedmioty: ";
   double p_waga[10000];
   for(int i=0; i<n; i++) // kolejne elementy do tablicy
   {
       cin>>p_waga[i];
   }

   sortuj(p_wart, p_waga, n);
   for(int i=0; i<n; i++)
   {

       sztuk = W / p_waga[i];
       W = W - sztuk*p_waga[i];
       wartosc = wartosc + sztuk * p_wart[i];

   }

   cout<<"Wartość plecaka to: "<<wartosc<<endl;
   return 0;
}

[Bono[UG] 1625]

Nadal masz nierówne rozmiary tablic.

 

Bo nie ma sensu robić pętli w pętli. Tam powinien być if, a nie while.

 

Teraz jak trochę dłużej popatrzyłem co tam się w pętli dzieje, to wydaje mi się, że nie liczy tego co trzeba. Próbujesz zapakować do plecaka wiele sztuk tego samego przedmiotu, a chyba nie o to chodzi w zadaniu.

Na marginesie ciekawe rozwiązanie o ile świadomie skorzystałeś z niejawnej konwersji typu double na int, wiesz co tam się dzieje i dlaczego to ma prawo działać.

 

Algorytm wydaje się prosty, sprawdzasz czy przedmiot mieści się w plecaku, jak tak to go ładujesz, jak nie to przechodzisz do kolejnego. Kontynuujesz aż skończą się przedmioty lub miejsce w plecaku.

 

Popracuj nad testowaniem czy program daje poprawne wyniki. To jest jeden z elementów szukania błędów w kodzie i algorytmie.

Podczas pisania programu warto sobie dodać więcej wypisów, żeby kontrolować poprawność działania (przy bardziej zaawansowanych programach można się pobawić w debuggera, gdzie można śledzić wykonanie programu krok po kroku, podejrzeć wartości zmiennych itp. rzeczy). Na koniec oczywiście trzeba je usunąć lub zakomentować.

Edytowane 21 Listopada 2019 przez Bono[UG]

[Roundstic 0]

To teraz to samo zadanie metodą dynamiczną( którą tak sobie ogarniam) coś źle mi liczy

 

#include <iostream>
using namespace std;

int main()
{
   int n;// przedmiotów
   int W; // pojemność plecaka/ waga


   cout<<" Podaj liczbę przedmiotów: ";
   cin>>n;

   cout<<" Podaj pojemność plecaka: ";
   cin>>W;

   cout<<"Wpisz wartosci przedmiotow: ";
  int c[1000];// cena przedmiotu
   for(int i = 0; i < n; i++)// kolejne liczby do tablicy
   {
       cin>>c[i];
   }

   cout<<"Wpisz ile zajmują te przedmioty: ";
   int w[10000];
   for(int i=0; i<n; i++) // kolejne elementy do tablicy
   {
       cin>>w[i];
   }


   int A[n + 1][W + 1]; //tworzę tablice o odpowiednim rozmiarze n- liczba przedmiotów W - pojemność plecaka


   // Przypisuje 0 do pierwszego wiersza i pierwszej komulny tablicy A

   for(int i=1; i<=W; i++)
   {
       A[i][0]=0;
   }

   for(int j=1; j<=n; j++)
   {
       A[0][j]=0;
   }
   // W dwóch zagnieżdżonych pętlach przeglądam komórki tablicy A uzupełniając je odpowiednimi wynikami
   for(int i=1; i<=W; i++)
   {
       for(int j=1; j<=n; j++)
       {
           if(w[j-1]>i)
           {
               A[i][j]= A[i][j-1];
           }
           else
           {
               A[i][j]=max(A[i][j-1], c[j-1]+A[i - w[i-1]][j - 1]);
           }
       }
   }

   cout<<A[W][n];

[Bono[UG] 1625]

Nie czytasz co się do ciebie pisze...

Trzeci raz zwracam uwagę, że masz nierówne rozmiary tablic.

 

Druga sprawa, to nie pędź tak do przodu. Skończ jedno do końca, potem baw się w zmiany.

 

 

Odnośnie zmian.

-czym jest tablica A? Co reprezentuje, jakie wartości przechowuje? Dlaczego zerujesz tylko pierwszą kolumnę i wiersz?

-brak opisu co się dzieje w tych zagnieżdżonych pętlach, nie wiadomo co autor miał na myśli, jak algorytm ma działać

 

Ciężko mi zatem cokolwiek podpowiedzieć co może być nie tak, zwłaszcza że nie podajesz przykładowego zestawu danych i oczekiwanego wyniku oraz jaki błędny wynik dostajesz.

Rzeczy mogą dziać się różne, od użycia niezainicjowanej pamięci w tablicach, przez błędne indeksy, po algorytm nie mający sensu.

 

Co mi się rzuciło w oczy bez głębszej analizy.

Dla w z elementami 10 1 prawdopodobnie wyjdziesz poza tablicę A, dla i==1 i j==2:

if(w[2-1]>1), czyli if(1>1) => warunek nie jest spełniony, w else Masz A[1-w[1-1]][2-1] czyli odwołujesz się do elementu A[1-10][1] czyli A[-9][1] => wychodzisz poza tablicę.

 

Druga kwestia, w warunku sprawdzasz tablicę w od indeksu j, w else odwołujesz się do tablicy w po indeksie i. Sprawdzasz jeden element, a wykorzystujesz inny.

[Roundstic 0]

Sam nie chciałbym tak pędzić, bo nie mogę niczego zrozumieć porządnie, ale taki plan studiów jest, na każdych ćwiczeniach coś nowego... Jak ktoś jest po rozszerzonej informatyce to jest mu łatwo, ale ja wszystko od samych podstaw ogarniam.

 

 

 

Tablica A[n + 1][W + 1] tablica do wypełnienia, gdzie sumaryczna wartość przedmiotu w optymalnym rozwiązaniu pod problemu, w którym pojemność plecaka to W, a wybieramy spośród n przedmiotów.

 

W zagnieżdżonych pętlach sprawdzam, czy waga i-tego przedmiotu jest większa niż przestrzeń dostępna w plecaku jeśli tak to A[j]=A[i-1][j] to jak jakby tego i-tego przedmiotu nie było

 

jeśli nie to

 

wybieram większą z tych wartości

 

A[i -1][j] - odpowiada przypadkowi kiedy nie wybieram optymalnego rozwiązania i-tego przedmiotu

 

ci+ A[i-1][j-wi] odpowiada przypadkowi kiedy wybieramy do optymalnego rozwiązania i-ty przedmiot czyli wybieramy korzystniejszą z tych 2 wartości

 

 

Teraz tak działam na takich danych

 

W=5 n=4

 

wi=5 1 3 1 /wagi

 

i odpowiednio ceny

 

ci= 8 2 10 5 / ceny

 

i teraz w najlepszym przypadku wartość plecaka to 17, a mi wychodzi 798761

 

#include <iostream>
using namespace std;

int main()
{
   int n;// przedmiotów
   int W; // pojemność plecaka/ waga


   cout<<" Podaj liczbę przedmiotów: ";
   cin>>n;

   cout<<" Podaj pojemność plecaka: ";
   cin>>W;

   cout<<"Wpisz wartosci przedmiotow: ";
  int c[10000];// cena przedmiotu
   for(int i = 0; i < n; i++)// kolejne liczby do tablicy
   {
       cin>>c[i];
   }

   cout<<"Wpisz ile zajmują te przedmioty: ";
   int w[10000];
   for(int i=0; i<n; i++) // kolejne elementy do tablicy
   {
       cin>>w[i];
   }


   int A[n+1][W+1]; //tworzę tablice o odpowiednim rozmiarze n- liczba przedmiotów W - pojemność plecaka


   // Przypisuje 0 do pierwszego wiersza i pierwszej komulny tablicy A

   for(int i=0; i<=n; i++)
   {
       A[i][0]=0;
   }

   for(int i=0; i<=W; i++)
   {
       A[0][i]=0;
   }
   // W dwóch zagnieżdżonych pętlach przeglądam komórki tablicy A uzupełniając je odpowiednimi wynikami
   for(int i=1; i<=n; i++)
   {
       for(int j=1; j<=W; j++)
       {
           if(w[i]>j)
           {
               A[i][j]= A[i-1][j];
           }
           else
           {
               A[i][j]=max(A[i-1][j], c[i]+A[i - 1][j - w[i]]);
           }
       }
   }

   cout<<A[n][W];
   return 0;
}

Edytowane 22 Listopada 2019 przez Roundstic

[Bono[UG] 1625]

U mnie pod Debianem i kompilowane gcc 4.7.2 wypisuje sensowną wartość 17.

Wypisz sobie zawartość całej tablicy A, po jej deklaracji. Być może pamięć przydzielana tablicy nie jest czysta i są tam jakieś bzdury.

 

Kolejna sprawa, to sprawdź wynik dla wagi pierwszego przedmiotu równej 2. Będzie błędnie podane 17 zamiast 18.

W pętlach w ogóle nie bierzesz pod uwagę pierwszego przedmiotu, bo pętle zaczynasz od 1. Musisz odwoływać się z indeksem pomniejszonym o 1 np. c[i-1]. Być może tu jest sedno problemu, bo wychodzisz poza wpisane przedmioty w tablicach (masz 4 przedmioty, czyli w tablicy są to indeksy 0, 1, 2, 3. W pętli dochodzisz do indeksu 4).

 

 

Odnośnie studiów, to taki ich urok, że trzeba sporo pracować samemu, a nie tylko tyle co na zajęciach.

W tym kontekście na pewno warto uczyć się szukania błędów. Sposoby są różne, od prześledzenia kodu, przez dodanie wypisów, korzystanie z debuggerów, assert-y, po ręczne liczenie na papierze.

 

Tutaj przykład jak to może wyglądać pod gdb (GNU debugger):

Breakpoint 3, main () at plecak.cpp:56
56	                A[i][j]=max(A[i-1][j], c[i]+A[i - 1][j - w[i]]]); <- linia kodu gdzie program został zatrzymany
(gdb) p {i,j,w[i],c[i]} <- wypisanie wartości zmiennych
$20 = {4, 1, 0, 0} <- wypisane wartości

Strzałki i opis dodane w ramach komentarza, normalnie ich nie ma.

Najpierw jest potrzebna kompilacja z flagą -g, żeby do programu zostały dodane informacje o kodzie. Następnie odpala się debugger i tam już działa. Większość środowisk programowania ma wbudowane funkcjonalności debbugerów.

 

Ustawiłem punkt przerwania na linię 56, odpaliłem program i gdb zatrzymał go na wskazanej linii. Wtedy dałem polecenie wypisania wartości zmiennych, następnie kontynuację wykonania i tak w kółko aż trafiłem na podaną wyżej sytuację.

U mnie w tablicach w i c po wyjściu poza obszar z wpisanymi przedmiotami jak widać są 0 ale u ciebie mogą być jakieś dziwne wartości.

 

 

Pilnuj indeksów tablic.

Pamiętaj, że zmienne mogą być niezainicjowane.