algorytm zachłanny- problem plecakowy

0

Witam czy mógłby mi ktoś doradzić jak zrobić aby dla algorytmu zachłannego wyswietlać produkty spakowane do plecaka.
Mam z tym problem , próbowałem to zrobić za pomocą tablicy dynamicznej struktury plecak{ int co_wlozono, int ile_wlozono} ale pojawia sie blad programu

0

http://pl.wikipedia.org/wiki/Problem_plecakowy

Przepisz algorytm i rozwiazanie bedzie jasne.

0

No to pokaż ten kod w którym pojawia się "błąd programu" lub przynajmniej podaj jaki błąd.

0

No ok więc teraz chciałem zrobić z tego procedury i całkiem nic nie działa może znajdziecie błąd i mi pomożecie, a zaraz napisze to wyswietlanie rzeczy spakowanych do plecaka ktore mi nie dzialalo.

#include <iostream>

using namespace std;

struct rzecz{
int wartosc;
int waga;
};
    int liczbaTypow;
    int wartosc_plecaka=0;
    int pojemnoscPlecaka;
    rzecz *rzeczy;
    rzecz pom;

void wczytajDaneOZ()
{
    cout<<"Podaj liczbe rodzzaji produktow: ";
    cin>>liczbaTypow;
    cout<<"Podaj pojemnosc plecaka: ";
    cin>>pojemnoscPlecaka;
    rzeczy=new rzecz[liczbaTypow+1];

    for(int i=1;i<=liczbaTypow;i++)
    {
        cout<<"Podaj wartosc przedmiotu nr: "<<i<<endl;
        cin>>rzeczy[i].wartosc>>rzeczy[i].waga;
    }
}
void sortowanie()
{
    for(int i=liczbaTypow-1;i>0;i--)
    {
        for(int j=0;j<i;j++)
        {
            if((double)rzeczy[i+1].wartosc/(double)rzeczy[i+1].waga>(double)rzeczy[i].wartosc/(double)rzeczy[i].waga)
            {   pom=rzeczy[i];
                rzeczy[i]=rzeczy[i+1];
                rzeczy[i+1]=pom;
            }
        }
    }

    for(int i=1;i<=liczbaTypow;i++)
    {
        cout<<rzeczy[i].wartosc<<" "<<rzeczy[i].waga;
        cout<<endl;
    }

}
void pakujPlecak()
{

     for(int i=0;i<liczbaTypow;i++)
    {
        if(rzeczy[i].waga<=pojemnoscPlecaka)
        {
            while(pojemnoscPlecaka>=rzeczy[i].waga)
              {
                wartosc_plecaka+=rzeczy[i].wartosc;
                pojemnoscPlecaka-=rzeczy[i].waga;
            }
        }
    }
        cout<<"Maksymalna wartosc plecaka wyniesie";
    cout<<endl<<wartosc_plecaka<<endl;

}
int main()
{
     wczytajDaneOZ();
     sortowanie();
     pakujPlecak();

 for (int i=1;i<=liczbaTypow;i++) // zwolnienie pamiêci
    {
    delete [] rzeczy;
    }
    return 0;
}
0

Przy wprowadzeniu nie wiedzieć czemu indeksujesz tablicę od 1.

To nie jest algorytm zachłanny tylko przybliżony.

0
_13th_Dragon napisał(a):

Przy wprowadzeniu nie wiedzieć czemu indeksujesz tablicę od 1

Po to abym miał pierwszy produkt o numerze 1 a nie 0.

0

Wszędzie pozmieniałeś indeksacje (nie słusznie) ale przy sortowaniu nadal jest indeksacja od 0.

0

Ok poprawie to ale nawet pomimo tego procedury powinny dać się wywołać w main'ie a mi to w ogóle nie działa. Na konsoli wyswietla mi tylko "Maksymalna wartosc plecaka wyniesie 0"

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0