Problem plecakowy z: Witam, muszę zaproponować układ równań dla problemu plecakowego o następujących założeniach. Złodziej rabujący sklep znalazł n przedmiotów kolejno; −1) o wadze 12 kg i łącznej wartości $4 −2) o wadze 4 kg i łącznej wartości $10 −3) o wadze 2 kg i łącznej wartości $2 −4) o wadze 1 kg i łącznej wartości $2 −5) o wadze 1 kg i łącznej wartości $1 Dąży on do zabrania jak najwartościowszego łupu, przy czym nie może zabrać przedmiotów o łącznej wadze większej niż 15 kilogramów. Nie może też zabierać ułamkowej części przedmiotów. Ponadto włamywaczna pewno chce wziąć przynajmniej jeden przedmiot 3) oraz przynajmniej jeden przedmiot 4) a na pewno nie chce wziąć przedmiotu 5). za x1,x2,x3,x4,x5 oznaczam kolejno wartości podanych przedmiotów i kolejno szukam x1+x2+x3+x4+x5 −> max Nie mam pomysłu jak mam uzależnić warunki co do maksymalnej wagi oraz ilości zabranych przedmiotów 3) i 4) od wartości przedmiotów.

z: Poprawka Złodziej rabujący sklep znalazł 5 przedmiotów po n sztuk każdy, kolejno;

Pytający: i∊{1, 2, 3, 4, 5} m_i // masa i−tego przedmiotu w_i // wartość i−tego przedmiotu k_i // ile sztuk i−tego przedmiotu zabrał ten złodziej k_i ∊ ℤ 0 ≤ k_i ≤ n dla i∊{1, 2, 5} 1 ≤ k_i ≤ n dla i∊{3, 4} ∑_i=1..5 (k_i*m_i) ≤ 15 Maksymalizujesz: ∑_i=1..5 (k_i*w_i)

Bleee: No to nadal zadanie jest stosunkowo łatwe bo: 1l pierwsza opcja w ogóle się nie opłaca i jej nie bierze (za ciężka a zysk niewielki).

	wartość
2| obliczamy		każdej opcji w celu wybrania najkorzystniejszej
	wagę

3| rozpatrujemy następujący przypadek: a) maksymalna możliwa waga najbardziej wartościowej opcji (2), później drugiej najbardziej opłacalne opcji (4). I to tyle. Żaden inny przypadek nie musi być rozpatrywany co można uzasadnić jeszcze jednym zdaniem.

Des: Prawdą jest, że do tego typu problemu nie można napisać 'uniwersalnego' skryptu? Takiego, który będzie działał dla dowolnego zbioru argumentów i wartości? Wykładowca od technologii twierdził, że dla jednego zbioru skrypt może działać, ale on jest w stanie znaleźć inny taki zbiór, dla którego skrypt się 'sypie'

Blee: więc po kolei 1) mamy nakazane, że bierzemy (min) 1 sztukę (3) i (min) 1 sztukę (4) i NIE BIERZEMY (5) więc nasza waga = 15 − 1*waga₃ − 1*waga₄ = 12kg 2) równanie: x₁*waga₁ + x₂*waga₂ + x₃*waga₄ + 0*waga₅ = 12 3)

	wartośći
liczymy wartośćjednostkowai =		dla każdego i mamy:
	wagai

	4
wartośćjednostkowa1 =		= 0.3
	12

	10
wartośćjednostkowa2 =		= 2.5
	4

	2
wartośćjednostkowa3 =		= 1
	2

	2
wartośćjednostkowa4 =		= 2
	1

4) czyli 'najbardziej opłaca' się brać (2) (największa wartość na jednostkę wagi) 5) piszemy procedurę (piszę 'pseudokod' ):

Pytający: O, tego że "nie chce wziąć przedmiotu nr 5" nie doczytałem. Znaczy w moim poście powinno być: 0 ≤ k_i ≤ n dla i∊{1, 2} 1 ≤ k_i ≤ n dla i∊{3, 4} k₅ = 0

Blee: Algorytm da się zrobić tak, że będzie działał dla dowolnego przypadku, ale to trochę zabawy będzie. Ogólnie będzie on zaczynał od maksymalizowania najbardziej optymalnych (największa wartoscjednostkowa, a przy takiej samej priorytetuje ten o niższej wadze). Zapamiętuje otrzymany wynik. Jeżeli pozostało jakieś miejsce to schodzi poziom niżej z ostatnim branym elementem. Zapisuje wynik. Jeżeli pozostało jakieś miejsce to schodzi poziom niżej z ostatnim branym elementem. Zapisuje wynik. Itd. Jeżeli w którymś miejscu 'wyzerował' jakiś element (pierwotnie wybierany) zaczyna schodzić z elementem 'poziom wyżej', resetując ilości wszystkich dalszych elementów.

z: Optymalne to już najlepsze! Nie może być coś "najbardziej optymalne" Dziękuje wszystkim za pomoc

Blee: ogólnie rzecz ujmując tak −−− jednak pisząc to miałem na myśli że algorytm będzie brał maksymalną liczbą OPTYMALNEGO argumentu i później dopełniał to 'kolejnymi (już nie optymalnymi) argumentami' które w tym momencie staną się optymalnym wyborem.