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

do góry

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

do góry

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

do góry

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

do góry

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

do góry

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.

do góry

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... )

do góry

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

do góry

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.)

do góry

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..

do góry