Cześć, jak przypisać koralowce do tablicy
int podzial[1];
Czyli:
podzial[0] = 0, 1, 5, 6
podzial[1] = 2, 3, 4, 7
Ważne jest do, żeby waga była równa albo minimalnie się od siebie różniła. Zarysowałem czerwonym kolorem, jakie powinno być podzielenie.
A coś więcej? Jakie warunki mają spełniać koralowce, ile ma ich być, co znaczy „minimalnie się różniła” przy wielu koralowcach, jaki jest rozmiar danych?
Waga poszczególnego koralowca nie przekroczy 1 000.
Ilość koralowców nie przekroczy 1 000 000.
Każdy koralowiec ma swój indeks (niech będzie j).
Koralowiec j = 0 ma wagę 1 i jest pierwszym koralowcem.
Koralowiec j = 1 ma wagę 1 i jest doklejony do koralowca 0.
Koralowiec j = 2 ma wagę 1 i jest doklejony do koralowca 1.
Koralowiec j = 3 ma wagę 1 i jest doklejony do koralowca 2.
I tak dalej...
Czyli, ta druga cyfra oznacza, do którego koralowca dokleja się koralowiec j = 1, ..., n-1
n-1 to liczba koralowców w rafie, w tym przypadku 8 (indeksy w tablicy).
Wielkość tablicy z wpisami jest definiowana pierwszą linijką z wejścia.
Cała ta rafa musi być podzielona na dwie takie same lub bardzo podobne do siebie wagowo.
W tym przypadku różnica między jedna, a drugą rafą wyniesie 0, więc podzieli po równo.
Nie mam pojęcia jak przypisać do tablicy podzielone koralowce i jak dorwać tę różnice.
Na wyjściu powinno być:
0 1
1 2
pierwsza linijka:
0 - minimalna różnica wag
1 - ilość kombinacji
druga linijka:
u v – koralowce które powinny się rozdzielić (u < v)
Drugi graf:
Są możliwe dwa podzielenia rafy koralowej
Ok, a więc. Wykorzystałem do do tego matrycę sąsiedztwa. Teraz wiem, który koralowiec łączy się z którym, a także z jaką wagą. Myślałem o matrycy sąsiedztwa trójkątnej, ale chyba nie tędy droga.
Kod:
#include <iostream>
#include <conio.h>
#include <string>
#include <fstream>
using namespace std;
int main()
{
int n;
const int size = 8;
int kor[size][2];
//odczyt koralowcow z pliku
fstream plik;
plik.open("in.txt", ios::in | ios::out);
if (plik.good() == true)
{
plik >> n;
plik >> kor[0][0];
kor[0][1] = 0;
for (int i = 1; i < n; i++)
{
plik >> kor[i][0];
plik >> kor[i][1];
}
plik.close();
}
//macierz sasiedztwa
int wmax, x, y;
int A[size][size];
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++) A[i][j] = 0;
wmax = 0;
for (int i = 1; i < n; i++)
{
x = i;
y = kor[i][1];
if (x > wmax) wmax = x; else wmax = wmax;
if (y > wmax) wmax = y; else wmax = wmax;
A[x - 1][y - 1] = kor[i][0];
A[y - 1][x - 1] = kor[i][0];
}
cout << endl;
for (int i = 0; i < wmax; i++)
{
cout << i+1 << ": ";
for (int j = 0; j < wmax; j++) cout << (int)A[i][j] << " ";
cout << endl;
}
system("PAUSE");
}
Pytanie. Jak rozdzielić te wszystkie koralowce na dwie rafy, żeby te rafy były wagowo takie same lub bardzo zbliżone do siebie. Oraz jak wyciągnąć, które koralowce powinny się rozdzielić.
Plik w załączniku
Po kolei dla każdego wierzchołka:
Czyli muszę napisać funkcję, która przeleci przez wszystkie wierzchołki zaczynając od wierzchołka j=1, 2,..., n-1?
Nie rozumiem natomiast jak cała reszta miałaby wyglądać. Mógłbyś napisać jeszcze bardziej łopatologicznie?
Bierzesz wierzchołek w. Ma on dzieci od d1 do dn , każde dziecko wyznacza poddrzewo. Liczysz wagę dla każdego poddrzewa z osobna. Teraz jeżeli wierzchołek w wyznacza granicę podziału, to są dwie sytuacje:
Ok, ale w jaki sposób mam zliczyć wagę każdej gałęzi? Wydaje się to logiczne, ale nie mam pojęcia jak wykryć, czy jest połączenie i z jakim wierzchołkiem.
Ruszże głową. Przejdź po poddrzewie DFS-em i zsumuj wagi.
Dobra, sumowanie wag ogarnięte. Wygląda to tak:
0: 0
Waga: 1
1: 1 0
Waga: 2
2: 2 1 0
Waga: 3
3: 3 2 1 0
Waga: 4
4: 4 3 2 1 0
Waga: 5
5: 5 1 0
Waga: 3
6: 6 1 0
Waga: 3
7: 7 4 3 2 1 0
Waga: 6
Aby kontynuować, naciśnij dowolny klawisz . . .
Moim wierzchołkiem z graniczną wagą to wierzchołek nr 7.
Wierzchołek 7 jest w podgrupie z 4, 3, 2, 1, 0 co łącznie daje wagę 6.
Druga podgrupa to 3, 6, co łącznie daje wagę 2.
Rozumiem, że teraz przelatuję przez każdy wierzchołek w grupie 1. Jeśli Suma + waga wierzchołka w-1 przekroczy połowę sumy wag wszystkich wierzchołków to wypisuje ten wierzchołek oraz wierzchołek w-1, z którym się łączy. Tak? Popraw mnie proszę jeśli się mylę.
A co ta Twoja tabelka z wagami przedstawia?
0:, 1:, 2:, itd to numer wierzchołka.
wartości po numerach wierzchołka to, wierzchołki, które się łączą z innymi wierzchołkami wraz z wierzchołkiem startowym.
np. 7: 7 4 3 2 1 0
Waga: 6
czyli:
w skład wierzchołka 7 wchodzi: wierzchołek 7, 4, 3, 2, 1, 0
łączna ich waga wynosi 6
No i ważne jest to, że póki co, każdy wierzchołek ma wagę 1. Mogę ci pokazać inny przykład z różnymi wagami.
No dobrze, a dlaczego w skład wierzchołka 5 wchodzą tylko 5, 1 i 0? Co z szóstką? Jak wyznaczasz skład? Wybacz, ale nie rozumiem, co Ty właściwie policzyłeś i w jakim celu.
Bo każdy wierzchołek jest połączony z jakimś (oprócz pierwszego w0)
Przechodzę po drzewie za pomocą DFS (graf skierowany)
Jakbym użył grafu nieskierowanego to by mi nic nie dało, bo za każdym razem bym miał wagę 8.
W żadnym momencie nie wspominałeś o skierowaniu. Co ono zmienia? Trzeba je uwzględniać przy wyznaczaniu podziału, jeżeli tak, to w jaki sposób? Mój algorytm nigdzie nie uwzględniał skierowania, bo nigdzie nie narysowałeś grafu skierowanego.
Szczerze mówiąc na pomysł z grafem skierowanym wpadłem niedawno. Wydaje mi się, że tak jest sensownie. Zobacz.
Wyciągam wierzchołek z największą wagą.
Czyli 7.
Wyznaczam wagę startową
Czyli 1, bo wierzchołek 7 ma wagę 1.
Lecę w-1 czyli w4.
Sumuję wagę
1 + 1 = 2
Lecę w-1 czyli w3
Sumuję wagę
2 + 1 = 3
Lecę w-1 czyli w2
Sumuję wagę
3 + 1 = 4
Jeśli 4 = 4 (łączna waga to 8. dzielę to na 2 bo chcę dwie rafy) to:
wypisuje wierzchołek aktualny czyli w2 i w-1 czyli w1.
Pytanie, czy będzie działać, jak będą możliwe dwa podziały
Piszesz tak nieskładnie, że szkoda czasu czytającego. Po pierwsze, wszystkie wierzchołki mają tę samą wagę, więc dlaczego wybrałeś wierzchołek 7? On nie ma największej wagi. Po drugie, zmień graf tak, żeby wierzchołki 0, 1, 5 i 6 wskazywały na wierzchołek 2 (a 2 nie wskazywał nigdzie), wtedy Twój algorytm się rozsypie, bo znajdzie grupę o wadze 4 (wierzchołki 7, 4, 3, 2), ale jak wrzuci dwójkę do tej grupy, to nie będzie mógł połączyć pozostałych wierzchołków. No chyba, że spójność nie ma znaczenia, ale tego w końcu nie wiem, bo nie raczyłeś odpowiedzieć na moje pytanie.
Zdecyduj się, co rozwiązujesz, opisz precyzyjnie wymogi, a potem nie zmieniaj ich w trakcie gry…
Piszesz klase strukture koral zeby było prosto koral ma pola publiczne id, CoralDoktóregoSieDoczepil, liste korali które doczepily sie do niego, wage.
Piszesz klase rafa. Rafa ma ma ppubliczny kontruktor z rozmiarem rafy, i metode add z waga korala i indeksem doczepienia or metode podziel zwracajaca nowa rafe.
Ma też prywatą tablice z listą korali. Zakładam że potrafisz napisać metode add tak zeby bylo dobrze(jako id w pisz index tablicy).
Ponieważ masz tylko jedno ciecie może się zdarzyć tak że korale ułoza sie w koło i nie bedzie mozliwe dokonanie podzialu. Poniewaz to jest parszywy special case zaczynasz od wyszukania cyklu w grafie, jesli znajdziesz zapisz wszystkie indeksy cyklu do (hash)tablicy. Jesli ilość w tych indeksów == rozmiarowi rafy nie ma dobrego podzialu. koniec.
Jesli nie skonczylo sie to teraz przeszukujesz dfs cała twoją tablice, zapisujesz na stos lub kolejski wszystkie corale do których doczypiony jest wiecej niż jeden koralowiec. Dla każdego korala w kolejce liczysz wage wszystkich korali doczepionych do niego, wyniki zapisujesz, List<coral,SumaWag>. Teraz liczysz sume wszystkich wag. Wybierasz najlepsze ciecie. Jesli miales cykl(dla prawidlowych danych moze byc tylko 1) to nie wolno Ci wybrać ciecia przerywającego cykl bo to nie tworzy nowej rafy.
Jesli chcesz by kod był "lepszy" to szukanie sum wag mozesz prosto rozwiazać programowaniem dynamicznym, a jeszcze lepiej by było gdby koral miał metode(też dynamiczna) liczenia ile waża dołaczone do niego korale.