Skocz do zawartości
Roundstic

Zadanie C++ plecak metoda zachłanna

Rekomendowane odpowiedzi

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;
}

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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 przez Roundstic

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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 przez Bono[UG]

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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;
}

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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 przez Bono[UG]

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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];

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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 przez Roundstic

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

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.

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się

  • Ostatnio przeglądający   0 użytkowników

    Brak zarejestrowanych użytkowników przeglądających tę stronę.

  • Tematy

  • Odpowiedzi

    • Ale tak bylo od wiekow to na prawde zejdz na ziemie i nie skladaj klockow. Wyplata opodatkowana a podatek od nieruchomopsci to calkowicie odmienne tematy. No masz racje na 2024 co wychodzi na duzy + bo drugi spada na 12% do 85K
    • @kola01Ok, dzięki za ogólne wyjaśnienie jak działają chłodzenia i stwierdzenie czy moje chłodzenie, którego nigdy w życiu na własne uszy nie słyszałeś jest ciche lub głośne😆 Bardzo wiele to zmienia w moim życiu, dobra robota👏  Jak "głośny" jest Fortis 5 dual przy swoim maksymalnym RPM 1400 w porównaniu z różnymi aio możesz przeczytać tutaj:  https://www.purepc.pl/test-silentiumpc-fortis-5-i-fortis-5-dual-fan-coolery-dla-procesorow-z-dobrym-stosunkiem-ceny-do-wydajnosci-i-cichymi-wentylator?page=0,7 Może uwierzysz 
    • Nic sobie nie pomyliłem. Z premedytacją nie użyłem nazwy gdyż mowiny o tanich asrocakch, model nie ma znaczenia. Ogólnie beka bo gdy mówię o karcie dźwiękowej narracja zmieniana jest na taką że dobra karta dźwiękowa nie jest potrzebna, można kupić inna, można kupić dac itp (TO SĄ DODATKOWE KOSZTY). Jak mówię o sekcji zasilania to narracja brzmi że pomylelem się z modelem płyty. Cały dowcip polega na tym że to 400zl to nie wiele jak na różnice w tym co dostajemy w tych mobasach. Tzn lepsza dźwiękowka, lepsza sekcja zasilania, lepsze wyposażenie. OGÓŁEM LEPSZA PŁYTA. Jeśli komuś wystarcza biedny kodek audio czy biedna sekcja zasilania to fajnie ale niech nie mówi że ta płyta jest dobra. Jest WYSTARCZAJĄCA dla niego i to wszystko. To tak jak z tymi bułkami z biedronki, dla kogoś są wystarczające, ja wolę kuoic 3x droższe i nie jest odnrazanego barachła. Argumenty że za 900zl płyty też mają kiepskie kodeki audio jest śmieszny bo wystarczy poszukać w specyfikacji technicznej i znaleźć taka która ma normalne audio, wyposażenie czy co tam nas interesuje. Nadal nikt nie odpowiedział, dlaczego nie polecają tanich asrockow na am4? Bo różnica pomiędzy dobrą płyta jest po prostu mniejsza i mówimy o mniejszej skali.  Edit: teraz spojrzałem na morele, nowy tomahawk kosztuje 871zl. Różnica pomiedzy "wystarczającymi" asrockami zaczyna topnieć wiec za niedługo ten post będzie nieaktualny bo i tak wszyscy będą polecali MSI. Obecnie to już 350zl czyli żaden pieniądz. 
    • Masz calkowita racje. 1 kwietnia lece na Florida zakupic dzialke i zaczac budowe domu. Nie dosc ze tax ma sprzedaz jest 6% to jak dom bedzie jako glowny nie bede placil stanowego podatku od zarobkow w moim wypadku to 10.75% ze stanu NJ. Tym sposobemdom wybuduje sie z tax z NJ.
    • No nie wiem jakim cudem ale w pit masz ustalone progi procentowe od zarobkow/ Kosz pracodawcy pracownika nic nie obchodzi bo to dwie oddzielne dzialalnosci. No to najprostrza droga. Z tego co sie orientuje to jak dobrze sie uczysz to studia nadal w Polsce sa bezplatne?.
  • Aktywni użytkownicy

×
×
  • Dodaj nową pozycję...