V stredu 19. 02. 2025 o 10:00h bude spustený jarný webinár zdarma. Na tomto webinári si ukážeme praktické ukážky monitorovania Prometheus endpointov s využitím nástroja Zabbix. Účastníci sa dozvedia, ako nastaviť a konfigurovať Zabbix na zber dát z prometheus exporterov vrátane vytvárania LLD pravidiel. Tento webinár je určený pre mierne pokročilých administrátorov Zabbixu. Registrácia na stránke: Axians Slovakia. Zoznam všetkých webinárov: Axians Slovakia webináre.
Byla vydána beta verze GNOME 48. Vyzkoušet lze instalační ISO GNOME OS. Vydání GNOME 48 je plánováno na březen.
Bochs (Wikipedie), tj. emulátor počítačů typu x86 a x86-64, byl vydán ve verzi 3.0.
Věříte své kalkulačce? Kolik je (10^100) + 1 − (10^100)? A kolik 1%−1%?
Na čem aktuálně pracují vývojáři GNOME a KDE Plasma? Pravidelný přehled novinek v Týden v GNOME a Týden v KDE Plasma.
FlappyFavi, hra Flappy Bird v ikoně Favicon. Nefunguje na mobilech.
Byly vyhlášeny výsledky (YouTube) 28. ročníku D.I.C.E. (Design, Innovate, Communicate, Entertain) Awards: Hrou roku 2024 je Astro Bot.
Všem na AbcLinuxu vše nejlepší k Valentýnu aneb Dni lásky ke svobodnému softwaru (I love Free Software Day, Mastodon, 𝕏).
Vývojáři openSUSE Tumbleweed oznámili, že u nových instalací se ve výchozím stavu přechází z AppArmor na SELinux. Uživatelé, kteří chtějí zůstat na AppArmor si mohou AppArmor vybrat v instalátoru.
Hector "marcan" Martin skončil jako vedoucí projektu Asahi Linux aneb Linux na Apple Siliconu. Projekt ale pokračuje dál.
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:
*_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
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 doDále lze v rekurzivních voláních
maxSkore
uvažovat pouze lexikálně stejně velké nebo vyšší trojice.
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)
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.
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.
# 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.
/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).
Tiskni
Sdílej: