Autor	Wiadomość
czart	Wysłany: Nie 18:55, 09 Gru 2007    Temat postu: I wszystko jasne, ja indeksuje od 0 i stad te rozbieznosci;] Z whilem to moj blad byl, jednak dobrze wszystko masz.
vbazyl	Wysłany: Nie 18:10, 09 Gru 2007    Temat postu: No mi to działa dobrze. A zwróć uwagę,że mam pętlę Kod:  for(i=1;i<=N;i++) trochę to dziwnie wygląda, ale u mnie program działa. A co do pętli Kod:  while(j) to j jest ta nasza waga, którą umieściliśmy w plecaku i teraz szukamy wag, których użyliśmy i odejmujemy je od j. I gdy wszystkie wagi znajdziemy to j nie może być przecież ujemne, ale równe 0. Aha już wyczaiłem czemu masz błąd. To jest moja funkcja wczytująca plik do tablicy (zwróć uwagę, że indeksuję nie od 0, ale od 1): Kod: void wczytaj_z_pliku(Ladunek tab[],int &N,int &K) {   ifstream we("in1.txt");   if(!we) cout<<"Blad!"<<endl;   we>>N;  // N<=20   we>>K;  // K<=100   for(int i=1;i<=N;i++)   {     we>>tab[i].w;     we>>tab[i].c;   }; };
czart	Wysłany: Nie 15:04, 09 Gru 2007    Temat postu: Kod:   while(j)   //tutaj szuka nr użytych  przedmiotów   {            //i zapisuje je do tablicy ptab     if(V[i][j]!=V[i-1][j])     {       j-=gtab[i].w;       ptab[z]=i;       z++;     };     --i;   }; Wydaje mi się ze ten kod jest bledny. Naprawde on u ciebie dziala ? Po pierwsze taka konstrukcja while zwiesza mi program :I. while(j>0) wyglada sensowniej. Dalej zamiast j-=gtab[i].w; powinno byc j-=gtab[i-1].w; gtab ma najwiekszy indeks N-1 a i na poczatku wynosi N. Reszta ok.
vbazyl	Wysłany: Pon 0:55, 03 Gru 2007    Temat postu: Już zamieściłem stosowne wyjaśnienia w kodzie. A te elementy najpierw zapisuję do tablicy ptab, a później do pliku wy1. Trzeba dodać bibliotekę <fstream> która obsługuje pliki.
chodor	Wysłany: Pon 0:20, 03 Gru 2007    Temat postu: u mnie ten sam problem niestety;/ i juz nie mam pomyslu jak to zrobic;/ moze cos sie do jutra wymysli noc przeciez dluga:)
czart	Wysłany: Nie 23:28, 02 Gru 2007    Temat postu: Hej bazyl, wszystko spoko, ale gdzie wypisujesz elementy ktore tworza wynik ... Reszte sam zrobilem, ale wlasnie nie moge sobie poradzic ze znalezieniem tych elementow :] (juz po obliczeniu najwiekszej wartosci)
vbazyl	Wysłany: Nie 21:53, 02 Gru 2007    Temat postu: Haha! Mam! ;] Chcecie? To popatrzcie na mój poprzedni post.
boro	Wysłany: Nie 21:24, 02 Gru 2007    Temat postu: mozna byloby sprobowac ale nie wiem czy to przejdzie. raz juz byl przelozony projekt. poza tym ostatnio mowila ze jestesmy do tylu z programami. no chyba ze sporo osob nie bedzie mialo dokonczonych programow wtedy mozna cos pokombinowac.
dynio	Wysłany: Nie 21:20, 02 Gru 2007    Temat postu: a może by ten projekt przełożyć na nast. tydzień ??
vbazyl	Wysłany: Nie 16:56, 02 Gru 2007    Temat postu: Tu są pewne pomysły do zad. 1 ;] http://www.koders.com/Default.aspx?s=knapsack&_%3Abtn=Search&_%3Ala=*&_%3Ali=*&p=1 http://www.lo2.opole.pl/~dragosystems/algorytmy/inne/plecak.htm http://4programmers.net/Algorytmy/Wprowadzenie_do_programowania_dynamicznego A to mój kod w cpp, ale nie wiem teraz jak sprawdzić, które przedmioty zostały wybrane (wypisuje tylko max wartość plecaka,czekam na pomysły): Edit: Kod został poprawiony i działa wszystko. Kod: class Ladunek {   public:   int w;  //waga   int c;  //cena   Ladunek()   {     w=0;     c=0;   }; }; void rozwiazanie1() {   Ladunek gtab[21];   int N=0,K=0;   wczytaj_z_pliku(gtab,N,K);   int V[N+1][K+1];   int i,j,pp;   V[0][0]=0;   for(i=1;i<=K;i++)     V[0][i]=-1;     for(i=1;i<=N;i++)     for(j=0;j<=K;j++)     {         pp=j-gtab[i].w;         if ((pp<0) || (V[i-1][pp]<0))           V[i][j]=V[i-1][j];       else         V[i][j]=max(V[i-1][pp]+gtab[i].c,V[i-1][j]);     };   int max=0;   for(j=0;j<=K;j++)   {      if( V[N][j]>V[N][max])        max=j;   };   ofstream wy1("out1.txt");   //otworzenie pliku do zapisu   i=N;   j=max;   int ptab[N];   int z=0;   while(j)   //tutaj szuka nr użytych  przedmiotów   {            //i zapisuje je do tablicy ptab     if(V[i][j]!=V[i-1][j])     {       j-=gtab[i].w;       ptab[z]=i;       z++;     };     --i;   };   for(i=z-1;i>=0;i--)  //przedmioty są wpisane "od tyłu" więc i tak je     wy1<<ptab[i]<<" "; //odczytujemy z ptab i zapisujemy do pliku wy1   wy1<<endl;        wy1<<V[N][max];       //a tu jest maksymalna wartość tych przedmiotów            };
wicher	Wysłany: Nie 14:39, 02 Gru 2007    Temat postu: Najlepiej żeby ktoś, kto ma cokolwiek (pomysł, algorytm, kod programu), podzielił się swoimi spostrzeżeniami na forum. Nie tylko do zadania 1 i 4 ale do wszystkich zadań. Wtedy metodą prób i błędów dojdziemy do poprawnych algorytmów. Co do zadania 4 to nie rozumiem za bardzo co miała na myśli. Jeśli ciąg oznacza dowolny "zlepek" znaków to moim zdaniem ciągi A i B można posortować, później porównując elementy z A i B wyszukać ten najdłuższy ciąg. Problem w tym, że proste porównania dają duży koszt algorytmu. Czyli tak na dobrą sprawę nic dobrego nie wymyśliłem.
czart	Wysłany: Nie 13:46, 02 Gru 2007    Temat postu: Ja mam podobny problem z zadaniem nr 1 . Nie wiem jak to ugryźć. Oba te zadania chyba podpadają pod programowanie dynamiczne którego do końca nie umiem zastasować . Sypnie ktoś pomysłem :>
boro	Wysłany: Nie 12:29, 02 Gru 2007    Temat postu: Mam problem bo zupelnie nie wiem jak zabrac sie do zadania ktore zamieszczam ponizej. Moze ma ktos jakis pomysl jak to rozwiazac? Zadanie 4 Grupa ambitnych studentów III roku wydziału informatyki chce złamać pewien szyfr i potrzebny jest im najszybszy algorytm rozwiązujący następujący problem. Dane są dwa ciągi znaków A i B. Należy znaleźć możliwie najdłuższy ciąg znaków występujący w obydwu ciągach A i B. Napisz program, który: 1. Wczyta z pliku in4.txt długości ciągów A i B oraz elementy tych ciągów 2. Wyznaczy długość najdłuższego ciągu znaków i wpisze tą długość oraz ten ciąg do pliku out4.txt (jeśli jest kilka takich ciągów to wystarczy wypisać jeden) Wejście: W pierwszym wierszu pliku in4.txt znajdują się dwie liczby całkowite oddzielone pojedynczą spacją n1 n2 oznaczające długości ciągów(n1, n2≤ 256). W kolejnych dwóch liniach tego pliku znajdują się ciągi znaków A i B. Wyjście: W pliku out4.txt w pierwszej jego linii jest wpisywana liczba całkowita, która oznacza długość najdłuższego ciągu występującego w obydwu zbiorach A i B. W kolejnej linii wypisywany jest ten ciąg znaków Przykład 1: Dla następującego pliku in4.txt 12 7 POLITECHNIKA TOALETA Plik out4.txt wygląda następująco: OLTA
vbazyl	Wysłany: Czw 21:11, 29 Lis 2007    Temat postu: A może ktoś wpadł na pomysł rozwiązania dyskretnego problemu plecakowego? Bo ja coś tam wymyśliłem, ale dla najgorszego przypadku obliczyłem, że rozwiązanie tego zajmie jakieś...1000 lat :P Tak więc proszę o podrzucenie pomysłu (najlepiej pomysł + kod hehe;)
boro	Wysłany: Sob 19:12, 24 Lis 2007    Temat postu: Algorytmy - Laboratorium PS_1 Ma ktoś może pdf z zadaniami /zestaw 4/ ? Asia nie działa i nie mam skąd wziąć treści zadan z laborek. Proszę o przesłanie mi pdf na piotr.borowik@wp.pl Z góry dzięki :]

Powered by phpBB © 2001, 2005 phpBB Group