Byla vydána nová verze 4.5 (𝕏, Bluesky, Mastodon) multiplatformního open source herního enginu Godot (Wikipedie, GitHub). Přehled novinek i s náhledy v příspěvku na blogu.
Byla vydána verze 3.0 (Mastodon) nástroje pro záznam a sdílení terminálových sezení asciinema (GitHub). S novou verzí formátu záznamu asciicast v3, podporou live streamingu a především kompletním přepisem z Pythonu do Rustu.
Canonical oznámil, že bude podporovat a distribuovat toolkit NVIDIA CUDA (Wikipedie) v Ubuntu.
Tržní hodnota americké společnosti Alphabet, která je majitelem internetového vyhledávače Google, dnes poprvé překonala hranici tří bilionů dolarů (62,1 bilionu Kč). Alphabet se připojil k malé skupině společností, které tuto hranici pokořily. Jsou mezi nimi zatím americké firmy Nvidia, Microsoft a Apple.
Spojené státy a Čína dosáhly dohody ohledně pokračování populární čínské platformy pro sdílení krátkých videí TikTok v USA. V příspěvku na síti Truth Social to dnes naznačil americký prezident Donald Trump. Dosažení rámcové dohody o TikToku vzápětí oznámil americký ministr financí Scott Bessent, který v Madridu jedná s čínskými představiteli o vzájemných obchodních vztazích mezi USA a Čínou. Bessentova slova později potvrdila také čínská strana.
MKVToolNix, tj. sada nástrojů pro práci s formátem (medialnym kontajnerom) Matroska, byl vydán ve verzi 95.0. Podpora přehrávání formátu Matroska míří do Firefoxu [Bug 1422891, Technický popis]. Přehrávání lze již testovat ve Firefoxu Nightly.
Spolek OpenAlt zve příznivce otevřených řešení a přístupu na 211. sraz, který proběhne v pátek 19. září od 18:00 ve Studentském klubu U Kachničky na Fakultě informačních technologií Vysokého učení technického na adrese Božetěchova 2/1. Na srazu proběhne přednáška Jiřího Eischmanna o nové verzi prostředí GNOME 49. Nemáte-li možnost se zúčastnit osobně, přednáškový blok bude opět streamován živě na server VHSky.cz a následně i zpřístupněn záznam.
Microsoft se vyhnul pokutě od Evropské komise za zneužívání svého dominantního postavení na trhu v souvislosti s aplikací Teams. S komisí se dohodl na závazcích, které slíbil splnit. Unijní exekutivě se nelíbilo, že firma svazuje svůj nástroj pro chatování a videohovory Teams se sadou kancelářských programů Office. Microsoft nyní slíbil jasné oddělení aplikace od kancelářských nástrojů, jako jsou Word, Excel a Outlook. Na Microsoft si
… více »Samba (Wikipedie), svobodná implementace SMB a Active Directory, byla vydána ve verzi 4.23.0. Počínaje verzí Samba 4.23 jsou unixová rozšíření SMB3 ve výchozím nastavení povolena. Přidána byla podpora SMB3 přes QUIC. Nová utilita smb_prometheus_endpoint exportuje metriky ve formátu Prometheus.
Správcovský tým repozitáře F-Droid pro Android sdílí doporučení, jak řešit žádosti o odstranění nelegálního obsahu. Základem je mít nastavené formální procesy, vyhrazenou e-mailovou adresu a být transparentní. Zdůrazňují také důležitost volby jurisdikce (F-Droid je v Nizozemsku).
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: