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.