Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #32423

Re: Problem plecakowy z wariantami

Show all headers | View raw

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.

Back to pl.comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Problem plecakowy z wariantami Borneq <borneq@antyspam.hidden.pl> - 2019-01-27 21:22 +0100
  Re: Problem plecakowy z wariantami Borneq <borneq@antyspam.hidden.pl> - 2019-01-27 21:27 +0100
    Re: Problem plecakowy z wariantami Borneq <borneq@antyspam.hidden.pl> - 2019-01-27 21:54 +0100
      Re: Problem plecakowy z wariantami Borneq <borneq@antyspam.hidden.pl> - 2019-01-27 21:56 +0100
        Re: Problem plecakowy z wariantami Roman Tyczka <noemail@because.no> - 2019-01-27 22:41 +0100
          Re: Problem plecakowy z wariantami fir <profesor.fir@gmail.com> - 2019-01-31 18:45 -0800
            Re: Problem plecakowy z wariantami "M.M." <mmarszik@gmail.com> - 2019-01-31 19:57 -0800
              Re: Problem plecakowy z wariantami fir <profesor.fir@gmail.com> - 2019-02-01 02:59 -0800
                Re: Problem plecakowy z wariantami fir <profesor.fir@gmail.com> - 2019-02-01 03:08 -0800
                Re: Problem plecakowy z wariantami "M.M." <mmarszik@gmail.com> - 2019-02-01 12:25 -0800
                Re: Problem plecakowy z wariantami fir <profesor.fir@gmail.com> - 2019-02-01 13:02 -0800
                Re: Problem plecakowy z wariantami fir <profesor.fir@gmail.com> - 2019-02-01 13:16 -0800
                Re: Problem plecakowy z wariantami stssasfe.seerea@gmail.com - 2019-02-01 16:36 -0800
                Re: Problem plecakowy z wariantami fir <profesor.fir@gmail.com> - 2019-02-02 02:13 -0800
                Re: Problem plecakowy z wariantami fir <profesor.fir@gmail.com> - 2019-02-03 13:10 -0800
                Re: Problem plecakowy z wariantami queequeg@trust.no1 (Queequeg) - 2019-02-19 14:03 +0000
                Re: Problem plecakowy z wariantami Roman Tyczka <noemail@because.no> - 2019-02-19 16:00 +0100
                Re: Problem plecakowy z wariantami queequeg@trust.no1 (Queequeg) - 2019-02-19 15:12 +0000
                Re: Problem plecakowy z wariantami Roman Tyczka <noemail@because.no> - 2019-02-19 16:38 +0100
                Re: Problem plecakowy z wariantami queequeg@trust.no1 (Queequeg) - 2019-02-19 15:42 +0000
      Re: Problem plecakowy z wariantami Borneq <borneq@antyspam.hidden.pl> - 2019-01-27 23:09 +0100

csiph-web