Podział na dwie równe części - programowanie liniowe?

Question

Zmarł bogaty arystokrata a jego spadek trzeba rozdzielić pomiędzy dwóch synów. W skład spadku wchodzą:

 A Caillebotte picture: 25000$
 A bust of Diocletian: 5000$
 A Yuan dinasty chinese vase: 20000$
 A 911 Porsche: 40000$
 Three blood diamonds: 12000$ each
 A Louis XV sofa: 3000$
 Two very fluffy rare breed cats: 3000$ each (the will asserts that they may not be separated)
 A sculpture dated 200 A.D.: 10000$
 A sailing boat: 15000$
 A Harley Davidson motorbike: 10000$
 A piece of furniture that once belonged to Newton: 13000$.

Wszystkie te przedmioty muszą być podzielone na dwie części. Jaki podział minimalizuje różnicę między wartościami dwóch części?

Jak sformułować taki program przy użyciu programowania liniowego? Mam z tym duży problem bo wszystkie problemy z którymi miałam styczność wcześniej opierały się jedynie na minimalizacji kosztów/maksymalizacji przychodów.

Comments

Prostee. Dzielisz wszystko na dwa i masz ile po równo każdy ma dostać.

---

Nie no, dzięki

Answer 1

W tym zadaniu funkcja celu może mieć postać:

A * x1 + B * x2 + C * x3 + D * x4 + .... + K * x11  =  A * y1 + B * y2 + C * y3 + D * y4 + ..... + K * y11

gdzie: A, B, C, D .... K są stałymi, oznaczającymi kolejne pozycje (wartości) spadku. (Np. A = 25000, B = 5000, C = 20000)

Lewa i prawa strona równania oznaczają odpowiednio: składniki spadku pierwszego i drugiego syna.

warunki można określić następująco:

x1 = 0 lub 1;      y1 = 0 lub 1;     x1 != y1;

x2 = 0 lub 1;      y2 = 0 lub 1;     x2 != y2;

x3 = 0 lub 1;      y3 = 0 lub 1;     x3 != y3;

...................................................

x11 = 0 lub 1;      y11 = 0 lub 1;     x11 != y11;

Jeśli któryś współczynnik: x lub y przyjmuje wartość 0, oznacza to, że danego składnika (czynnika) w "worku" syna nie ma.

Mają funkcję celu oraz tak sformuowane warunki można już stosunkowo łatwo, numerycznie znaleźć wartości wszystkich współczynników x i y, dla których nastąpi równy podział majątku (lub najbardziej zbliżony do równego).

Answer 2

1. Wprowadź cały spadek - wszystkie rzeczy (wartości) do kontenera.

2. Zrób sortowanie od najmniejszej wartości - do największej.

3. Utwórz dwie zmienne A i B reprezentujące dwóch synów, gdzie będą sumowane spadki w ich "workach".

4. Z kontenera pobieraj kolejno parami wartości, poczynając od największych, i rozdzielaj między dwa zbiory A i B. Każdorazowo sprawdzaj jaka jest sumaryczna wartość każdego z nich. Jeśli, któraś będzie wyższa, to z pary pobranych wartości przydziel mniejszą. Tak postępuj do końca (do wyczerpania wszystkich rzeczy).

Comments

Ale nie jest to chyba zdefiniowanie problemu przy użyciu programowania liniowego? To co podałeś jest algorytmem zachłannym.