-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.P
OSTED!not-for-mail
From: Borneq <b...@a...hidden.pl>
Newsgroups: pl.comp.programming
Subject: Re: Problem plecakowy z wariantami
Date: Sun, 27 Jan 2019 23:09:40 +0100
Organization: ATMAN - ATM S.A.
Lines: 107
Message-ID: <q2la75$5ao$1@node1.news.atman.pl>
References: <q2l3te$gf3$1@node2.news.atman.pl> <q2l47n$gk9$1@node2.news.atman.pl>
<q2l5pd$i3m$1@node2.news.atman.pl>
NNTP-Posting-Host: public-gprs353591.centertel.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1548626981 5464 37.47.12.120 (27 Jan 2019 22:09:41 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Sun, 27 Jan 2019 22:09:41 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101
Thunderbird/60.4.0
In-Reply-To: <q2l5pd$i3m$1@node2.news.atman.pl>
Content-Language: pl
Xref: news-archive.icm.edu.pl pl.comp.programming:213346
[ ukryj nagłówki ]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.
Następne wpisy z tego wątku
- 01.02.19 03:45 fir
- 01.02.19 04:57 M.M.
- 01.02.19 11:59 fir
- 01.02.19 12:08 fir
- 01.02.19 21:25 M.M.
- 01.02.19 22:02 fir
- 01.02.19 22:16 fir
- 02.02.19 01:36 s...@g...com
- 02.02.19 11:13 fir
- 03.02.19 22:10 fir
- 19.02.19 15:03 Queequeg
- 19.02.19 16:00 Roman Tyczka
- 19.02.19 16:12 Queequeg
- 19.02.19 16:38 Roman Tyczka
- 19.02.19 16:42 Queequeg
Najnowsze wątki z tej grupy
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-04-26 steve balmer o iphonie w 2007
- 2024-04-25 Wrocław => Java Developer <=
- 2024-04-25 Kraków => AI Specialist <=
- 2024-04-25 Berlin => Solution Architect (secure communication and IoT solutions)
- 2024-04-25 Gdańsk => Specjalista ds. Sprzedaży <=
- 2024-04-25 Problemy TSMC cd
- 2024-04-25 Kraków => Senior PHP Developer (Symfony) <=
- 2024-04-25 Katowice => Service Leader/PLC Programmer with German <=
- 2024-04-25 Białystok => ERP Implementer <=
- 2024-04-25 O wisienkach
- 2024-04-25 Warszawa => Interactive/Experience Designer <=
- 2024-04-25 Białystok => Wdrożeniowiec ERP <=
- 2024-04-25 Wrocław => Head of Sales (IT services/products field) <=
- 2024-04-25 Berlin => IT Systems Administrator and Customer Support Engineer <=
- 2024-04-25 Warszawa => Technical Lead ( (Java Background)) <=