Portál AbcLinuxu, 8. května 2025 17:48
Zdravím a prosím o pomoc s algoritmickým řešením následující úlohy:
Je dáno:
Pravidla:
Cílem je získat pro daný mix v pytlíku nejvíce bodů.
Díky za postrčení.
P.S. Hladový algoritmus? Generický algoritmus? Něco jiného? Jak na to? Nějaké knihovny atd.? Řešit to potřebuju v PHP.
Řešení dotazu:
13.7.2015 15:06
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Jediné na co jsem přišel je:
1) genetický algoritmus, ale snažím se najít přímočařejší řešení... v tomhle oboru nemám moc zkušeností.
2) hladový algoritmus, teda snažit se volit nejziskovější kombinaci co jde.
To zahození je dobrý nápad! Určitě zjednoduší problém... můžu zahodit horší nebo stejné kombinace složené ze stejných kamenů.
13.7.2015 16:43
Jendа | skóre: 78
| blog: Jenda
| JO70FB
*_kamenů >= 0 integer kombinace1 = 19 bodů kombinace2 = 11 bodů ... červených_kamenů = 2*kombinace1 + kombinace2 + ... ... červených_kamenů <= kolik_máš_červených_kamenů ... ct = sum kombinace*; max ct; solve
13.7.2015 16:38
Jendа | skóre: 78
| blog: Jenda
| JO70FB
jelikož u té menší již znáte maximální skóre, je snadné spočítat maximální skóre i pro tu většíPokud znám nejlepší řešení pro 1 trojici a 2 trojice, nevidím jak snadno najít nejlepší řešení pro tří trojice. Jde najít kombimace, kdy v nejlepším řešení pro tři trojice nebude žádná trojice, která je v nejlepších řešeních pro 1 resp. 2 trojice.
maxSkore budou cachovat):
// poctyKamenu je pole. poctyKamenu[i] oznacuje, kolik kusu i-teho kamene mame.
function maxSkore(poctyKamenu)
m = 0
for i = 1 .. 9 do
for j = 1 .. 9 do
for k = 1 .. 9 do
if poctyKamenu umoznuji vybrat trojici (i, j, k) then
od poctyKamenu odecti kameny pouzite v (i, j, k)
m = max(maxSkore(poctyKamenu) + skore trojice (i, j, k), m)
k poctyKamenu pricti kameny pouzite v (i, j, k)
end if
end for
end for
end for
end function
m, to jsem zapomněl.
for i = 1 .. 9 do
for j = i .. 9 do
for k = j .. 9 do
Dále lze v rekurzivních voláních maxSkore uvažovat pouze lexikálně stejně velké nebo vyšší trojice.
13.7.2015 22:39
Jendа | skóre: 78
| blog: Jenda
| JO70FB
integer podmínku, tak to asi nenajde optimum, ale řešení by mohlo být „docela dobré“ a spočítá se rychle).
x(1) = 3 x(2) = 9 ... x(n) = k(n)Dále mám nějaké kameny, to vyjádřím:
y(1) = 100 // tím zavedu počet kamenů, možná by mělo být y(m) <= k(m) ale to je detail y(2) = 23 ... y(9) = 11Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)? Podle mého nikdy nedostanu do jedné (ne)rovnice x(n) a y(m), protože hodnota kamenu není konstanta... Uniká mi něco?
Musím tedy volit jako proměnné trojice kamenůAno. Trojice kamenů očísluji 1-729 a
x(i) bude vyjadřovat, kolikrát vyberu trojici s číslem i.
Je-li c(i) konstanta s cenou trojice číslo i, pak chceme maximalizovat c(1)*x(1) + … + c(729)*x(729) s tím, že počty použitých kamenů nesmí přesáhnout počty kamenů na vstupu.
Tj. označíme-li n(1), …, n(9) počty kamenů na vstupu, pak pro každé n(j) musí platit:
(suma x(i) takových, že trojice číslo i obsahuje právě jeden kámen j) +
2 * (suma x(i) takových, že trojice číslo i obsahuje právě dva kameny j) +
3 * (suma x(i) takových, že trojice číslo i obsahuje právě tři kameny j) <= n(j)
14.7.2015 13:03
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Trochu sem to pročetl a nevidím způsob, jak to na úlohu LP nasadit.Napsal jsem to výše. (btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepší)
Pak to bude vypadat tak, že budu mít několik set funkcíAno, to není problém, třeba můj úkol pro předmět ze kterého pochází ten manuál měl 10k funkcí a výpočet trval pár sekund.
Otázka teď ale zní, jak vyjádřím závislost x(n) na kamenech - tedy y(m)?Vyrobíš si proměnné z(1) .. z(n), které značí, kolikrát jsi kterou kombinaci použil. Potom vyrobíš proměnné a(1) .. a(9), které v závislosti na vektoru z ukazují, kolik kamenů jsi využil.
a(1) = 1*z(1) + 2*z(2) + 1*z(4)pokud v kombinaci 1 je 1 kámen barvy 1, v kombinaci 2 jsou 2 kameny barvy 2, v kombinaci 3 žádný atd. Pak už jenom zadáš podmínky že nesmíš použít víc kamenů než máš
a(1) <= y(1)Pak zadáš účelovou funkci - součet ohodnocení * kolikrát ta kombinace padla
ct = z(1)*x(1) + z(2)*x(2) + .. + z(n)*x(n)A řešíš pro
max ctAle jak jsem psal, pokud to jde iterativně dynamicky, dá to lepší výsledek a nejspíš to doběhne i rychleji.
btw. pokud to jde tím dynamickým programováním jak napsal Radek výše, tak to je mnohem lepšíObávám se, že pro větší počet kamenů to je nepraktické. Například pro 100 kamenů celkem existuje 108! / 100! / 8! možných devític.
14.7.2015 15:34
Jendа | skóre: 78
| blog: Jenda
| JO70FB
Do cache se dostane každá kombinace, tedy i všechny kombinace 10 trojicCache je 9-rozměrné pole o hranách kolik_kamenů_od_té_barvy_máme, ne? Takže pro 20 kusů od každého kamene je to „jenom“ 20^9 * sizeof(uint64) = 4 TB.
14.7.2015 15:36
Jendа | skóre: 78
| blog: Jenda
| JO70FB
# x(i) ... promenna kolikrat jsem pouzil kombinaci i (vůbec nebo libovolně krát)
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;
var x5 >= 0;
var x6 >= 0;
var x7 >= 0;
var x8 >= 0;
var x11 >= 0;
...
var x729 >= 0;
# c(i) ... hodnota kombinace i (dané konstanty)
var c1 = 6;
var c2 = 5;
var c3 = 6;
var c4 = 5;
var c5 = 5;
var c6 = 7;
var c7 = 8;
var c8 = 9;
var c9 = 5;
var c11 = 4;
...
var c729 = 3;
# vstupy a(i) - kolik mám kamenů daných typů (nerovnost, protože nemusím použít všechny)
var a1 <= 6;
var a2 <= 0;
var a3 <= 0;
var a4 <= 0;
var a5 <= 0;
var a6 <= 0;
var a7 <= 0;
var a8 <= 0;
var a9 <= 0;
# a(n) ... pocet pouzitych kamenu n... tohle je dáno zadáním - např. kombinace 1 je ze 3 kamenu typu 1, proto je v a1 člen 3*x1
v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4 + ...
v2: a2 = 0 + 1*x2 + 2*x11 + 1*x12 + 1*x13 + ...
v3: a3 = 0 + 1*x3 + 1*x12 + 2*x21 + 1*x22 + ...
v4: a4 = 0 + 1*x4 + 1*x13 + 1*x22 + 2*x31 + ...
v5: a5 = 0 + 1*x5 + 1*x23 + 1*x32 + 2*x41 + ...
v6: a6 = 0 + 1*x6 + 1*x15 + 1*x24 + 1*x33 + ...
v7: a7 = 0 + 1*x7 + 1*x25 + 1*x34 + 1*x43 + ...
v8: a8 = 0 + 1*x8 + 1*x17 + 1*x26 + 1*x35 + ...
v9: a9 = 0 + 1*x9 + 1*x27 + 1*x36 + 1*x45 + ...
# ucelova fce ct = c(1)*x(1) + c(2)*x(2) + .. + c(n)*x(n) - vždy násobím hodnotu kombinace krát počet jejích užití... celkový součet maximalizuji
maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4 + c5*x5 + c6*x6 + ...
solve;
end;
Ty kombinace jsem zkrátil - teda vybral vždy jen jen tu nejlepší permutaci pro danou trojici kamenů - zbylo 165 kombinací.
Netušíte, v čem je zakopaný pes a co je špatně?
multiplication of linear forms not allowedNemůže být problém v tom, že násobíte proměnné jinýmy proměnnými? Místo c1, c2 atd. bych zkusil použít přímo konkrétní čísla.
14.7.2015 22:16
Jendа | skóre: 78
| blog: Jenda
| JO70FB
/tmp> cat lin.mod var x1 >= 0; var x2 >= 0; var x3 >= 0; var x4 >= 0; param c1 := 6; param c2 := 5; param c3 := 6; param c4 := 5; var a1 <= 6; var a2 <= 0; var a3 <= 0; var a4 <= 0; v1: a1 = 0 + 3*x1 + 2*x2 + 2*x3 + 2*x4; v2: a2 = 0 + 1*x2; v3: a3 = 0 + 1*x2; v4: a4 = 0 + 1*x3; maximize ct: 0 + c1*x1 + c2*x2 + c3*x3 + c4*x4; solve; end; /tmp> glpsol -m lin.mod GLPSOL: GLPK LP/MIP Solver, v4.55 Parameter(s) specified in the command line: -m lin.mod Reading model section from lin.mod... 24 lines were read Generating v1... Generating v2... Generating v3... Generating v4... Generating ct... Model has been successfully generated GLPK Simplex Optimizer, v4.55 5 rows, 8 columns, 15 non-zeros Preprocessing... 1 row, 2 columns, 2 non-zeros Scaling... A: min|aij| = 1.000e+00 max|aij| = 2.000e+00 ratio = 2.000e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part is 1 * 0: obj = 1.200000000e+01 infeas = 0.000e+00 (0) * 1: obj = 1.500000000e+01 infeas = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (102316 bytes) Model has been successfully processedNo a tohle ti najde řešení, které když zaokrouhlíš, tak asi bude nějak „přiměřeně dobré“ (v tom předmětu ze kterého to pochází se pak třeba dokazuje jestli takto získané řešení není více než 2x horší než skutečné optimum atd.). Když za "x" proměnné napíšeš "integer" (var x1 >= 0, integer;), tak to najde optimum, ale asi to bude počítat dýl (obecně až exponenciálně dlouho).
obecně až exponenciálně dlouhoObecně i Simplex počítá exponenciálně dlouho (lineární programy lze však řešit v polynomiálním čase – například elipsoidovou metodou).
14.7.2015 22:32
Jendа | skóre: 78
| blog: Jenda
| JO70FB
.
Vím, a gplk neimplementuje elipsoidovou metodu?
Tiskni
Sdílej:
ISSN 1214-1267, (c) 1999-2007 Stickfish s.r.o.