Mam taki problem: jest x paczek każda o objętości V i wadze y (każda o innej), ciężarówki mają pojemność V=100. Jak załadować każdą ciężarówkę, by waga paczek w każdej ciężarówce była jak najblizej średniej, czyli, żeby każdy ładunek mozliwie tyle samo ważył?
0
0
Przyszedł mi do głowy taki prosty pomysł co do wagi:
Posegreguj paczki od najlżejszej do najcięższej i ładuj je do każdej ciężarówki po kolei parami - najlżejsza paczka i najcięższa paczka.
0
to w sumie niezłe rozwiązanie, szybkie i powinno być blisko średniej, choć gorzej jak liczba paczek nie będzie taka by równo podzielić wielokrotnosci 2 do każdej ciężarówki np 5 ciężarówek i 16 paczek.
0
możesz to zmodyfikować sortując nie po samej wadze ale po iloczynie wagi i objętości lub wagi, objętości i współczynniku. Współczynnik należało by dobrać doświadczalnie. Jeśli liczba paczek nie dzieli się przez liczbę ciężarówek to trzeba zrobić paczki mod ciężarówki i tyle najmniejszych rozłożyć po jednej do każdej ciężarówki (np. 16 paczek, 5 ciężarówek - 16 mod 5 = 1 więc najpierw 1 najmniejszą paczkę wkładasz do ciężarówki nr 1 a potem po 2 do każdej i na końcu po 1 do każdej)
0
Ale co jest tutaj priorytetem? Zaladowanie jak najwiekszej ilosci paczek czy rownomierne rozdzielenie paczek?
0
załadowanie wszystkich paczek, zeby ich waga w każdej ciężarówce była zbliżona
0
Mozesz uzyc Mixed Integer Programming do rozwiazania tego zadania.
Wrzucasz to do jakiegos MIP solvera (np. google or tools) i masz rozwiazanie.
0
co to jest wi? I ten mip solver to rozumiem jakaś biblioteka z tego co widzę? Niestety to nie da rady, bo nie da się dołączyć jej do programu.Muszą być tylko standardowe biblioteki javy.
0
wi to waga paczki i.
Tak MIP solver jest zazwyczaj w formie zewnetrznej biblioteki. Jak nie mozesz uzyc niczego z zewnatrz to mip odpada. Najprosciej chyba bedzie uzyc local search - local move to moze byc swap 2 paczek pomiedzy dwoma samochodami.