Forum PCLab.pl: Zadanie C++ plecak metoda zachłanna - Forum PCLab.pl

Skocz do zawartości

Otwarty

Ikona Ostatnio dodane tematy

Ikona Najnowsze pliki

Strona 1 z 1
  • Nie możesz rozpocząć nowego tematu
  • Nie możesz odpowiadać w tym temacie

Zadanie C++ plecak metoda zachłanna Oceń temat: -----

#1 Użytkownik jest niedostępny   Roundstic 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 24
  • Dołączył: Wed, 13 Lis 19

Napisany 20 Listopad 2019 - 19:43

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[i] <= 10000 oraz wartościach 0 <= c[i] <= 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;
}


#2 Użytkownik jest niedostępny   Roundstic 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 24
  • Dołączył: Wed, 13 Lis 19

Napisany 20 Listopad 2019 - 21:24

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

Ten post był edytowany przez Roundstic dnia: 20 Listopad 2019 - 21:24


#3 Użytkownik jest niedostępny   Bono[UG] 

  • Wiecznie niewyspany...
  • PipPipPipPipPip
  • Grupa: Forumowicze
  • Postów: 20381
  • Dołączył: Pt, 27 Wrz 02

Napisany 21 Listopad 2019 - 09:19

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.

Ten post był edytowany przez Bono[UG] dnia: 21 Listopad 2019 - 09:21


#4 Użytkownik jest niedostępny   Roundstic 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 24
  • Dołączył: Wed, 13 Lis 19

Napisany 21 Listopad 2019 - 12:23

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


#5 Użytkownik jest niedostępny   Bono[UG] 

  • Wiecznie niewyspany...
  • PipPipPipPipPip
  • Grupa: Forumowicze
  • Postów: 20381
  • Dołączył: Pt, 27 Wrz 02

Napisany 21 Listopad 2019 - 13:11

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ć.

Ten post był edytowany przez Bono[UG] dnia: 21 Listopad 2019 - 13:14


#6 Użytkownik jest niedostępny   Roundstic 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 24
  • Dołączył: Wed, 13 Lis 19

Napisany 21 Listopad 2019 - 16:07

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


#7 Użytkownik jest niedostępny   Bono[UG] 

  • Wiecznie niewyspany...
  • PipPipPipPipPip
  • Grupa: Forumowicze
  • Postów: 20381
  • Dołączył: Pt, 27 Wrz 02

Napisany 21 Listopad 2019 - 18:06

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.

#8 Użytkownik jest niedostępny   Roundstic 

  • Dyskutant
  • PipPip
  • Grupa: Forumowicze
  • Postów: 24
  • Dołączył: Wed, 13 Lis 19

Napisany 22 Listopad 2019 - 10:56

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[i][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;
}

Ten post był edytowany przez Roundstic dnia: 22 Listopad 2019 - 10:57


#9 Użytkownik jest niedostępny   Bono[UG] 

  • Wiecznie niewyspany...
  • PipPipPipPipPip
  • Grupa: Forumowicze
  • Postów: 20381
  • Dołączył: Pt, 27 Wrz 02

Napisany 22 Listopad 2019 - 12:42

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.

Strona 1 z 1
  • Nie możesz rozpocząć nowego tematu
  • Nie możesz odpowiadać w tym temacie

1 Użytkowników czyta ten temat
0 użytkowników, 1 gości, 0 anonimowych