eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Problem plecakowy z wariantami
Ilość wypowiedzi w tym wątku: 16

  • 1. Data: 2019-01-27 21:22:05
    Temat: Problem plecakowy z wariantami
    Od: Borneq <b...@a...hidden.pl>

    Wariant polega na tym, że rozmiar plecaka może się wahać i to w dużym
    zakresie od n do 2*n.
    Bez wahania rozmiaru stosuje się na przykład do zapytania o wypalenia na
    płytach CD/DVD a mi chodzi o to, że kompresujemy blokami, nie za
    wielkimi i nie za małymi i dane łączymy w bloki od n do 2*n (przy czym
    wszystkie elementy są mniejsze od n, więc nie trzeba się tym kłopotać)
    tak by nie zostawało bloków typu 0.1n czy większych niż 2*n


  • 2. Data: 2019-01-27 21:27:35
    Temat: Re: Problem plecakowy z wariantami
    Od: Borneq <b...@a...hidden.pl>

    W dniu 27.01.2019 o 21:22, Borneq pisze:
    > Wariant polega na tym, że rozmiar plecaka może się wahać i to w dużym
    > zakresie od n do 2*n.
    > Bez wahania rozmiaru stosuje się na przykład do zapytania o wypalenia na
    >  płytach CD/DVD a mi chodzi o to, że kompresujemy blokami, nie za
    > wielkimi i nie za małymi i dane łączymy w bloki od n do 2*n (przy czym
    > wszystkie elementy są mniejsze od n, więc nie trzeba się tym kłopotać)
    > tak by nie zostawało bloków typu 0.1n czy większych niż 2*n
    Może po prostu

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

    Algorytm aproksymacyjny: "Jeśli k jest maksymalną wartością przedmiotów
    w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie
    gorsze niż k/2"
    czyli gdyby chodziło o dokładny problem, to było by niezbyt dobrze, ale
    w przypadku takim ja ja chcę, to jest akurat


  • 3. Data: 2019-01-27 21:54:06
    Temat: Re: Problem plecakowy z wariantami
    Od: Borneq <b...@a...hidden.pl>

    W dniu 27.01.2019 o 21:27, Borneq pisze:
    > https://pl.wikipedia.org/wiki/Problem_plecakowy

    z drugiej strony nie chodzi mi o to by jeden plecak był najlepiej
    wypełniony, ale by było jak najmniej plecaków


  • 4. Data: 2019-01-27 21:56:33
    Temat: Re: Problem plecakowy z wariantami
    Od: Borneq <b...@a...hidden.pl>

    W dniu 27.01.2019 o 21:54, Borneq pisze:
    > W dniu 27.01.2019 o 21:27, Borneq pisze:
    >> https://pl.wikipedia.org/wiki/Problem_plecakowy
    >
    > z drugiej strony nie chodzi mi o to by jeden plecak był najlepiej
    > wypełniony, ale by było jak najmniej plecaków
    czyli co innego: https://en.wikipedia.org/wiki/Bin_packing_problem


  • 5. Data: 2019-01-27 22:41:17
    Temat: Re: Problem plecakowy z wariantami
    Od: Roman Tyczka <n...@b...no>

    On Sun, 27 Jan 2019 21:56:33 +0100, Borneq wrote:
    > W dniu 27.01.2019 o 21:54, Borneq pisze:
    >> W dniu 27.01.2019 o 21:27, Borneq pisze:
    >>> https://pl.wikipedia.org/wiki/Problem_plecakowy
    >>
    >> z drugiej strony nie chodzi mi o to by jeden plecak był najlepiej
    >> wypełniony, ale by było jak najmniej plecaków
    > czyli co innego: https://en.wikipedia.org/wiki/Bin_packing_problem

    Bloga sobie załóż.

    https://www.blogger.com/blogger.g#welcome

    --
    pozdrawiam
    Roman Tyczka


  • 6. Data: 2019-01-27 23:09:40
    Temat: Re: Problem plecakowy z wariantami
    Od: Borneq <b...@a...hidden.pl>

    W dniu 27.01.2019 o 21:54, Borneq pisze:
    > W dniu 27.01.2019 o 21:27, Borneq pisze:
    >> https://pl.wikipedia.org/wiki/Problem_plecakowy
    >
    > z drugiej strony nie chodzi mi o to by jeden plecak był najlepiej
    > wypełniony, ale by było jak najmniej plecaków

    Mam coś takiego :
    int knapsack_first(int capacity)
    {
    vector<int> v = { 200,130,70,20,1,10,15,25,30,120 };
    vector<int> bins;
    sort(v.begin(), v.end(), compare);
    bins.push_back(capacity);
    for (int i = 0; i < v.size(); i++)
    {
    int w = v[i];
    if (w > capacity) continue;
    bool found = false;
    for (int j = 0; j < bins.size(); j++)
    {
    if (w <= bins[j])
    {
    bins[j] -= w;
    found = true;
    break;
    }
    }
    if (!found)
    {
    bins.push_back(capacity);
    bins.back() -= w;
    }
    }
    cout << capacity << " " << bins.size() << endl;
    return bins.size();
    }

    int main()
    {
    knapsack_first(140);
    }

    Cztery pojemniki.
    Dla pierwszych trzech bardzo dobrze zadziałało, wszystkie wypełnione w
    100 %, ale w czwartym jest tylko jedynka.
    A jak zrobić by było bardziej równomiernie? np po 105-106 w każdym czyli
    trochę ponad 75%
    To szukam najbardziej pustego
    int knapsack_best(int capacity)
    {
    vector<int> v = { 200,130,70,20,1,10,15,25,30,120 };
    vector<int> bins;
    sort(v.begin(), v.end(), compare);
    bins.push_back(capacity);
    for (int i = 0; i < v.size(); i++)
    {
    int w = v[i];
    if (w > capacity) continue;
    int found = -1;
    int maxFree = w;
    for (int j = 0; j < bins.size(); j++)
    {
    if (bins[j]>=maxFree)
    found = j;
    }
    if (found >= 0)
    {
    bins[found] -= w;
    }
    else
    {
    bins.push_back(capacity);
    bins.back() -= w;
    }
    }
    cout << capacity << " " << bins.size() << endl;
    return bins.size();
    }
    Zdesperowany od razu tworzę 4 zamiast jednego i robię knapsack_best,
    sytuacja taka że tylko pierwszy jest z jedynką, reszta zapełniona.


    W
    https://en.wikipedia.org/wiki/Bin_packing_problem

    Modified first fit decreasing (MFFD)[7] improves on FFD for items larger
    than half a bin by classifying items by size into four size classes
    large, medium, small, and tiny, corresponding to items with size > 1/2
    bin, > 1/3 bin, > 1/6 bin, and smaller items respectively. Then it
    proceeds through five phases:

    Allot a bin for each large item, ordered largest to smallest.
    Proceed forward through the bins. On each: If the smallest
    remaining medium item does not fit, skip this bin. Otherwise, place the
    largest remaining medium item that fits.
    Proceed backward through those bins that do not contain a medium
    item. On each: If the two smallest remaining small items do not fit,
    skip this bin. Otherwise, place the smallest remaining small item and
    the largest remaining small item that fits.
    Proceed forward through all bins. If the smallest remaining item of
    any size class does not fit, skip this bin. Otherwise, place the largest
    item that fits and stay on this bin.
    Use FFD to pack the remaining items into new bins.

    nie za bardzo rozumiem, może to pomaga?
    Kubełków i tak i tak jest 4, ale chciałem bardziej równomiernie.


  • 7. Data: 2019-02-01 03:45:31
    Temat: Re: Problem plecakowy z wariantami
    Od: fir <p...@g...com>

    W dniu niedziela, 27 stycznia 2019 22:41:18 UTC+1 użytkownik Roman Tyczka napisał:
    > On Sun, 27 Jan 2019 21:56:33 +0100, Borneq wrote:
    > > W dniu 27.01.2019 o 21:54, Borneq pisze:
    > >> W dniu 27.01.2019 o 21:27, Borneq pisze:
    > >>> https://pl.wikipedia.org/wiki/Problem_plecakowy
    > >>
    > >> z drugiej strony nie chodzi mi o to by jeden plecak był najlepiej
    > >> wypełniony, ale by było jak najmniej plecaków
    > > czyli co innego: https://en.wikipedia.org/wiki/Bin_packing_problem
    >
    > Bloga sobie załóż.
    >
    > https://www.blogger.com/blogger.g#welcome
    >
    wg mnie problemem broneq jest nie tyle ze
    pisze posty i na nie odpowiada - tylko ze jego pisaniny sa nieciekawe i natchnione
    jakas denna szajba - W pewnym sensie traktuje broneq jako parodie czy moze raczej
    karykature samego siebie tyle ze zdecydowan ie niezbyt udana ;c (nardzio wasko
    zakresowa i z dolaczona glupota i szajbą)

    broneq nie spelnie podstawowych wymogow, np nie potrafi nawet zadac poprawnie pytania
    o tyle robi wrazenie inwalidy umyslowego, (itd itd, o tyle dolaczylbym go do znanego
    zestawu inwalidow umyslowych jak np ramine i spolka... )


  • 8. Data: 2019-02-01 04:57:02
    Temat: Re: Problem plecakowy z wariantami
    Od: "M.M." <m...@g...com>

    On Friday, February 1, 2019 at 3:45:32 AM UTC+1, fir wrote:
    > W dniu niedziela, 27 stycznia 2019 22:41:18 UTC+1 użytkownik Roman Tyczka napisał:
    > > On Sun, 27 Jan 2019 21:56:33 +0100, Borneq wrote:
    > > > W dniu 27.01.2019 o 21:54, Borneq pisze:
    > > >> W dniu 27.01.2019 o 21:27, Borneq pisze:
    > > >>> https://pl.wikipedia.org/wiki/Problem_plecakowy
    > > >>
    > > >> z drugiej strony nie chodzi mi o to by jeden plecak był najlepiej
    > > >> wypełniony, ale by było jak najmniej plecaków
    > > > czyli co innego: https://en.wikipedia.org/wiki/Bin_packing_problem
    > >
    > > Bloga sobie załóż.
    > >
    > > https://www.blogger.com/blogger.g#welcome
    > >
    > wg mnie problemem broneq jest nie tyle ze
    > pisze posty i na nie odpowiada - tylko ze jego pisaniny sa nieciekawe i natchnione
    jakas denna szajba - W pewnym sensie traktuje broneq jako parodie czy moze raczej
    karykature samego siebie tyle ze zdecydowan ie niezbyt udana ;c (nardzio wasko
    zakresowa i z dolaczona glupota i szajbą)
    >
    > broneq nie spelnie podstawowych wymogow, np nie potrafi nawet zadac poprawnie
    pytania o tyle robi wrazenie inwalidy umyslowego, (itd itd, o tyle dolaczylbym go do
    znanego zestawu inwalidow umyslowych jak np ramine i spolka... )


    Co słychać Kapitanie Fir, bo u nas po staremu:
    https://img3.dmty.pl//uploads/481_600.jpg

    Pozdrawiam


  • 9. Data: 2019-02-01 11:59:42
    Temat: Re: Problem plecakowy z wariantami
    Od: fir <p...@g...com>

    W dniu piątek, 1 lutego 2019 04:57:03 UTC+1 użytkownik M.M. napisał:
    > On Friday, February 1, 2019 at 3:45:32 AM UTC+1, fir wrote:
    > > W dniu niedziela, 27 stycznia 2019 22:41:18 UTC+1 użytkownik Roman Tyczka
    napisał:
    > > > On Sun, 27 Jan 2019 21:56:33 +0100, Borneq wrote:
    > > > > W dniu 27.01.2019 o 21:54, Borneq pisze:
    > > > >> W dniu 27.01.2019 o 21:27, Borneq pisze:
    > > > >>> https://pl.wikipedia.org/wiki/Problem_plecakowy
    > > > >>
    > > > >> z drugiej strony nie chodzi mi o to by jeden plecak był najlepiej
    > > > >> wypełniony, ale by było jak najmniej plecaków
    > > > > czyli co innego: https://en.wikipedia.org/wiki/Bin_packing_problem
    > > >
    > > > Bloga sobie załóż.
    > > >
    > > > https://www.blogger.com/blogger.g#welcome
    > > >
    > > wg mnie problemem broneq jest nie tyle ze
    > > pisze posty i na nie odpowiada - tylko ze jego pisaniny sa nieciekawe i
    natchnione jakas denna szajba - W pewnym sensie traktuje broneq jako parodie czy moze
    raczej karykature samego siebie tyle ze zdecydowan ie niezbyt udana ;c (nardzio wasko
    zakresowa i z dolaczona glupota i szajbą)
    > >
    > > broneq nie spelnie podstawowych wymogow, np nie potrafi nawet zadac poprawnie
    pytania o tyle robi wrazenie inwalidy umyslowego, (itd itd, o tyle dolaczylbym go do
    znanego zestawu inwalidow umyslowych jak np ramine i spolka... )
    >
    >
    > Co słychać Kapitanie Fir, bo u nas po staremu:
    > https://img3.dmty.pl//uploads/481_600.jpg
    >
    > Pozdrawiam

    no u mnie raczej po nowemu, sporo sie zmienilo, mniej koduje wiecej zajmowalem sie
    innymi sprawami (tyle ze problemy ze zdrowiem ciezkie jak zawsze, a moze i gorsze)
    obecnie akurat traumatyczny czas, bo dentysta wyrwal mi 1/4 szczeki tj dwa duze zemby
    w tym jeden podstepnie bez pytania o zgode (i zastanawiam sie czy latac po prawnikach
    i jak, z wielka rana i szwami w gebie)

    jest tak srednio dla mnie to dosyc trudny czas, duzo rozmaitych przygod (typu gadanie
    z tymi lub tamtymi) ale i zarazem zmeczenie ponadprzecietne i wysoka intoksykacje
    syfem na ktory jestem chory - slowem nie jestem pewien czy jest powod by mi
    zazdroscic.. duzo pracy ktore przetwaza sie na potezne zuzycie mnie samego
    (psychiczne i fiz.)


  • 10. Data: 2019-02-01 12:08:26
    Temat: Re: Problem plecakowy z wariantami
    Od: fir <p...@g...com>

    W dniu piątek, 1 lutego 2019 11:59:43 UTC+1 użytkownik fir napisał:
    >slowem nie jestem pewien czy jest powod by mi zazdroscic..

    powiedzialbym "nie sadze"

    jak zawsze robia jakies tam ciekawe i wazne rzeczy ale zmeczenie i zjechanie jakie to
    generuje jest oblesne i raczej nie powoduje ze jestem zbyt 'szczesliwy' (troche jak
    czlowiek zbyt zmeczony by zasnac) wiekszosc ludzi podejrzewam czuje sie lepiej wiec
    definitywnie nie polecam..

strony : [ 1 ] . 2



Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: