Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[Zadanie] "Wartości ciągów "

Ostatnio zmodyfikowano 2011-07-10 13:14
Autor Wiadomość
kamillo121
Temat założony przez niniejszego użytkownika
[Zadanie] "Wartości ciągów "
» 2011-07-09 18:00:23
Problem:
Dane są dwa zbiory ciągów znakowych:
W każdym ze zbiorów znajdują się unikatowe ciągi, czyli nigdy nie dojdzie do powtórzenia.

Pierwszy zbiór ciągów znaków prócz znaków posiada jeszcze wagę ciągu np: 

ciąg: ABC  waga:   15
ciąg: DECA  waga:  13
ciąg: TSU  waga:   10
ciąg: DAW  waga:   9
ciąg: ABCEA  waga:   7

Drugi zbiór ciągów znaków posiada jedynie znaki np:
ciąg: ABC  
ciąg: DECA
ciąg: ABCEA

Muszę uzyskać poszczególne liczby dla każdego ciągu ze zbioru drugiego oznaczające możliwie największą ilość wystąpień przy możliwie największej ilości ciągów ze zbioru drugiego i największej ogólnej wartości ciągów ze zbioru drugiego kierując się skalą ze zbioru pierwszego na np 10 wyników. Tolerancja dla wartości a ilości to np 30. czyli jak będą np. dwa wyniki
Pierwszy:
wartość 80
ilość 3

Drugi
wartość 100
ilość 2

To w tym wypadku bardziej wartościowy jest Pierwszy wynik ponieważ ilość jest ważniejsza niż wartość przy tolerancji 30.

By przybliżyć problem podam kilka możliwych wyników dla powyższych zbiorów:
Ilość ogólnych wystąpień: 10

Pierwsza możliwość

ciąg: ABC    wystąpienia:  5 
ciąg: DECA   wystąpienia:  3
ciąg: ABCEA   wystąpienia:  2

Ogólna wartość to: 75+39+14
Ilość ciągów to: 3

Druga możliwość

ciąg: ABC   wystąpienia:  10 

Ogólna wartość to: 150
Ilość ciągów to: 1

Trzecia możliwość

ciąg: ABC   wystąpienia:  6 
ciąg: DECA  wystąpienia:  4

Ogólna wartość to: 90+52
Ilość ciągów to: 2

Najlepszym wynikiem z tych trzech jest Pierwsza możliwość przy zachowaniu tolerancji 40.

Czy moglibyście mi podać jakieś algorytmy matematyczne które mogłyby mnie przybliżyć do celu ? cokolwiek nazwę pojęcia matematycznego, algorytmu.
Coś o co mógłbym się "oprzeć" podczas pisania kodu.
Jak coś to treść tego problemu nie jest żadnym konkursem,zadaniem itp
 
//próbuję wyszukać funkcje matematyczne które pomogą mi w uzyskaniu wyniku dlatego, że kod będzie bardziej elastyczny na zmiany i może szybszy (prędkość w tym wypadku jest kluczowa)
P-35635
DejaVu
» 2011-07-09 19:54:51
Nie rozumiem ;p
P-35657
kamillo121
Temat założony przez niniejszego użytkownika
» 2011-07-09 20:17:29
Spróbuję to prościej wytłumaczyć:
Jeden agregat przechowuje taką strukturę danych:
C/C++
struct Slo
{
    char * slowo;
    short waga;
};

Pole waga określa jakość słowa, im większa waga tym większy priorytet dla słowa.

Przykładowo mamy taki zbiór :

ciąg: ABC   waga:   15
ciąg: DECA  waga:   13
ciąg: TSU   waga:   10
ciąg: DAW   waga:   9
ciąg: ABCEA waga:   7

Teraz mamy drugi agregat który przechowuje tylko same ciągi znakowe np:

ciąg: ABC  
ciąg: DECA
ciąg: ABCEA

Na wyjściu chce uzyskać np. 10 słów z drugiego agregatu (tego gdzie są dla przykładu 3 ciągi) słowa mogą byś powtarzane kilka razy zależnie od zestawu słów(a co za tym idzie od wagi). Teraz muszę wygenerować taki zestaw słów z agregatu drugiego (tego gdzie są dla przykładu 3 ciągi) by zawierał on możliwie jak najwięcej różnych słów i suma wagi wszystkich tych słów była możliwie jak największa ale słowa te mogą być rzecz jasna tylko z tego drugiego agregatu, pierwszy agregat jest tylko do sprawdzania wagi słowa. Dodatkowo jeżeli np jeden obliczony zestaw ma ogólną wagę  140 i 4 różne słowa(powtórzone kilka razy by osiągnąć 10) a drugi zestaw ma ogólną wagę 120 i 6 słów(powtórzone kilka razy by osiągnąć 10) to lepsza jakość zestawu jest wybierana na podstawie tej tolerancji. Dla przykładu niech będzie tolerancja zmniejszonej wagi 30 czyli z powyższego przykładu wybrany byłby zestaw, który ma wagę 120 i 6 słów dlatego że mieści się w tolerancji utraty wagi ale ma więcej różnych słów.
Szukam tutaj małej pomocy ze strony matematyki bo sprawdzanie każdego możliwego zestawu potrwa za długo a to mają być dynamiczne obliczenia.
Nawet przyjmując, że drugi agregat będzie miał max 30 słów i będę chciał wybrać np 20 na wyjściu to obliczenie każdej możliwej sytuacji i jej analiza potrwa za długo(to by było jakieś po 30 możliwości na każde z przykładowych 20 miejsc czyli  30^20 chyba, że źle pamiętam metodę obliczania możliwych kombinacji).

//Dodam tylko, że ten algorytm nie musi mieć 100% trafności i wybierać tylko najsilniejsze zestawy bo słowa dobierane są precyzyjne a waga słów i tolerancja i tak zmienia się wraz ze wzrostem natężenia danego słowa obliczanego w innym algorytmie. Ten algorytm ma wybrać proponowany zestaw(o tak to ujmę).
P-35661
ison
» 2011-07-10 02:46:07
Dobra, udało mi się zrozumieć ;)
Najbardziej psuje sprawę ten zakres tolerancji, lepiej byłoby gdyby najpierw decydowała o wyniku ilość słów a potem dopiero waga ale to by było za proste :D
Jakiej złożoności oczekujesz?

abym się upewnił, że dobrze zrozumiałem:
ciąg: ABC  waga:   15
ciąg: DECA  waga:  13
ciąg: TSU  waga:   10
ciąg: DAW  waga:   9
ciąg: ABCEA  waga:   7

Drugi zbiór ciągów znaków posiada jedynie znaki np:
ciąg: ABC 
ciąg: DECA
ciąg: ABCEA
w tym przypadku niektóre ciągi z pierwszego zbioru są zbędne, tak?
czyli można to równie dobrze przedstawić jako
ciąg: ABC waga: 15
ciąg: DECA waga: 13
ciąg: ABCEA waga: 7


//
ok, jeśli dobrze zrozumiałem treść zadania:

złożoność: O(n log n)
1. tworzysz sobie struktury tak jak powyżej (wyrazenie,waga)
2. sortujesz je względem wag (O(n log n))
3. tworzysz sobie tablicę z wynikami
4. do elementu tab[1] zapisujesz sumę wag jakie możesz uzyskać biorąc jedynie wyrażenie o największej wadze (wyrazenie_o_najwiekszej_wadze.waga * ilosc_wyrazen_jakie_mamy_wziac)
5. do elementu tab[2] zapisujesz sumę wag jakie możesz uzyskać biorąc n-1 wyrażeń o największej wadze (gdzie n to ilość dostępnych różnych wyrażeń) oraz 1 wyrażenie kolejno niżej z największą wagą
6. do elementu tab[3] zapisujesz sumę wag jakie możesz uzyskać biorąc n-2 wyrażeń o największej wadze, 1 wyrażenie kolejno niżej z największą wagą, 1 wyrażenie kolejno niżej z największą wagą
7. itd...
tab:
Ilosc wyrazen: (i)                             1 2 3 4 5 6 7 8 9 ...
Maksymalna możliwa waga do uzyskania: (tab[i]) ... ... ... ...
tab[i] to maksymalna możliwa waga do uzyskania dla i różnych wyrażeń
8. teraz wybierasz elementy z tablicy tab[i] które są w zakresie max(tab[i])-ZAKRES_TOLERANCJI do max(tab[i]) (gdzie max to największa wartość jaką zawiera tablica)
9. z wybranych elementów wybierasz ten, który ma najwięcej różnych wyrażeń (czyli ten o największym i)

(rozwiązanie polega na tym, że zawsze przecież najbardziej opłaca się brać te wyrażenia o największej wadze a ilościowo dopełniać po jednym innym słowie z mniejszą wagą, nigdy nie opłaca się brać 3 elementów o największej wadze i 2 elementów o wadze niższej skoro można wziąć 4 elementy o największej wadze i 1 element o wadze niższej nie tracąc przy tym ilości różnych wyrażeń)

//edit
(złożoność taka jaką podałem wyżej, dla n log n program działa w sensowym czasie nawet dla 1000000 ciągów):
C/C++
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

const int TOLERANCJA = 40;

class Cwyrazenie
{
public:
    std::string str;
    int waga;
   
    //zmienna pomocnicza
    int suma_do_mnie; //zmienna zawiera sumę wag po jednym z każdego elementu posortowanego ciągu wyrażeń licząc od końca nie licząc ostatniego elementu
    //wprowadzone aby zredukować złożoność z pow(n,2) do n log n
   
    Cwyrazenie() { }
    Cwyrazenie( const std::string new_str, const int new_waga )
        : str( new_str )
        , waga( new_waga )
    {
    }
    ~Cwyrazenie() { }
};

class Cwyrazenie_max
{
public:
    int ilosc_roznych_wyrazen;
    int maksymalna_waga;
   
    Cwyrazenie_max() { }
    Cwyrazenie_max( const int new_ilosc_roznych_wyrazen, const int new_maksymalna_waga )
        : ilosc_roznych_wyrazen( new_ilosc_roznych_wyrazen )
        , maksymalna_waga( new_maksymalna_waga )
    {
    }
    ~Cwyrazenie_max() { }
};

bool wyrazenie_mniejsze( const Cwyrazenie wyr1, const Cwyrazenie wyr2 )
{
    return wyr1.waga < wyr2.waga;
}

int main()
{
    std::vector < Cwyrazenie > wyrazenie;
    int n, ilosc_wyrazen;
    scanf( "%d", & n ); //n czyli liczba różnych wyrażeń do dyspozycji, n musi wynosić przynajmniej 1
    std::string tmp_str;
    int tmp_waga;
    for( int i = 0; i < n; ++i ) {
        std::cin >> tmp_str >> tmp_waga;
        wyrazenie.push_back( Cwyrazenie( tmp_str, tmp_waga ) );
    }
    sort( wyrazenie.begin(), wyrazenie.end(), wyrazenie_mniejsze );
    if( wyrazenie.size() >= 2 )
         for( int i = int( wyrazenie.size() - 2 ); i >= 0; --i ) {
        if( i == int( wyrazenie.size() - 2 ) ) wyrazenie[ i ].suma_do_mnie = wyrazenie[ i ].waga;
        else wyrazenie[ i ].suma_do_mnie = wyrazenie[ i ].waga + wyrazenie[ i + 1 ].suma_do_mnie;
       
    }
    scanf( "%d", & ilosc_wyrazen ); //ilosc_wyrazen musi wynosic przynajmniej 1
    int * suma_wag = new int[ std::min(( int ) wyrazenie.size(), ilosc_wyrazen ) + 1 ];
    for( int i = 0; i < std::min(( int ) wyrazenie.size(), ilosc_wyrazen ); ++i ) {
        suma_wag[ i + 1 ] = wyrazenie[ wyrazenie.size() - 1 ].waga *( ilosc_wyrazen - i );
        if( i != 0 ) suma_wag[ i + 1 ] += wyrazenie[ wyrazenie.size() - 1 - i ].suma_do_mnie;
       
    }
    int maksymalna_mozliwa_waga =- 1;
    for( int i = 1; i < std::min(( int ) wyrazenie.size(), ilosc_wyrazen ) + 1; ++i ) {
        if( suma_wag[ i ] > maksymalna_mozliwa_waga ) maksymalna_mozliwa_waga = suma_wag[ i ];
       
    }
    std::vector < Cwyrazenie_max > wyrazenie_max;
    for( int i = 1; i < std::min(( int ) wyrazenie.size(), ilosc_wyrazen ) + 1; ++i ) {
        if( suma_wag[ i ] >= maksymalna_mozliwa_waga - TOLERANCJA ) wyrazenie_max.push_back( Cwyrazenie_max( i, suma_wag[ i ] ) );
       
    }
    int best_indeks = 0;
    int max_ilosc_roznych_wyrazen =- 1;
    for( size_t i = 0; i < wyrazenie_max.size(); ++i ) {
        if( wyrazenie_max[ i ].ilosc_roznych_wyrazen > max_ilosc_roznych_wyrazen ) {
            max_ilosc_roznych_wyrazen = wyrazenie_max[ i ].ilosc_roznych_wyrazen;
            best_indeks = i;
        }
    }
    printf( "%d\n", wyrazenie_max[ best_indeks ].maksymalna_waga );
}

dla pierwszego testu, który podałeś (przy zachowaniu tolerancji 40) najlepszym możliwym wynikiem jest 140
P-35674
kamillo121
Temat założony przez niniejszego użytkownika
» 2011-07-10 13:08:32

nigdy nie opłaca się brać 3 elementów o największej wadze i 2 elementów o wadze niższej skoro można wziąć 4 elementy o największej wadze i 1 element o wadze niższej nie tracąc przy tym ilości różnych wyrażeń

Otóż nie, o wybraniu zestawu słów decyduje właśnie ilość słów o ile utrata wagi mieści się w zakresie tolerancji. W tym wypadku dla mnie bardziej wartościowy jest zestaw, który ma mniej wagi np o 30 a więcej słów np o 2 niż ten który ma więcej wagi a mniej słów.
Nie może to być na zasadzie wybierania najpierw największej ilości słów o największej wadze a potem na dopełnianiu bo liczy się różnorodność słów.
P-35701
ison
» 2011-07-10 13:11:22
Otóż nie, o wybraniu zestawu słów decyduje właśnie ilość słów o ile utrata wagi mieści się w zakresie tolerancji. W tym wypadku dla mnie bardziej wartościowy jest zestaw, który ma mniej wagi np o 30 a więcej słów np o 2 niż ten który ma więcej wagi a mniej słów
napisałem, że przy tym nie tracimy ilości słów (3 elementy A i 2 elementy B VS 4 elementy A i 1 element B)

Nie może to być na zasadzie wybierania najpierw największej ilości słów o największej wadze a potem na dopełnianiu bo liczy się różnorodność słów.
wuut? teraz to już totalnie nie rozumiem, czyli tak: chcesz mieć największą wagę, najwięcej słów a przy tym największą różnorodność słów biorąc pod uwagę wystąpienie każdego z nich? Trochę dziwne mi się zdaje ale ok ;P
P-35702
DejaVu
» 2011-07-10 13:14:15
1. robisz strukturę:
C/C++
struct Ble
{
    int waga;
    int ileSlow;
};
2. Robisz kontener:
C/C++
std::vector < Ble > bla;
3. Wrzucasz obliczenia do kontenera:
C/C++
for( int i = 0; i < 123; i++ )
     bla.push_back( Ble( _waga_, _ile_slow_ ) );

4. Sortujesz malejąco:
C/C++
std::sort( bla.begin(), bla.end() );
5. Odczytujesz najwyższe wyniki.

strukturę wystarczy uzupełnić o odpowiedni konstruktor i operatory <, ==, != i zadanie teoretycznie powinno być gotowe. Co dla Ciebie jest ważniejsze określasz w operatorze mniejszości.
P-35704
« 1 »
  Strona 1 z 1