Čínská společnost Tencent uvolnila svůj AI model HunyuanWorld-Voyager pro generování videí 3D světů z jednoho obrázku a určené trajektorie kamery. Licence ale nedovoluje jeho používání na území Evropské unie, Spojeného království a Jižní Koreje.
Blender Studio se spojilo s kapelou OK Go a výsledkem je videoklip k písni Impulse Purchase. Stejně jako samotný 3D software Blender je i ve videoklipu použitý animovaný chlápek open source. Kdokoli si jej může stáhnout a upravovat.
Zig Software Foundation stojící za programovacím jazykem Zig publikovala finanční zprávu za rok 2024. Současně s prosbou o finanční příspěvek.
Na čem pracují vývojáři webového prohlížeče Ladybird (GitHub)? Byl publikován přehled vývoje za srpen (YouTube). Vypíchnuta je podpora Tabulek Google, implementace Gamepad API a Cookie Store API nebo také podpora WebGL na Linuxu.
openSUSE Leap 16, včetně Leap Micra 6.2+, nově nabízí 24 měsíců podpory pro každé vydání. To je dva roky aktualizací a stability, což z něj činí nejdéle podporovanou komunitní distribuci vůbec. Leap se tak stává ideální platformou pro všechny, kdo hledají moderní, stabilní a dlouhodobě podporovanou komunitní Linux distribuci.
Národní úřad pro kybernetickou a informační bezpečnost (NÚKIB) vydal dne 3. 9. 2025 VAROVÁNÍ před hrozbou v oblasti kybernetické bezpečnosti spočívající v předávání systémových a uživatelských dat do Čínské lidové republiky a ve vzdálené správě technických aktiv vykonávané z území Čínské lidové republiky. Varováním se musí zabývat povinné osoby podle zákona o kybernetické bezpečnosti.
Americká internetová společnost Google nemusí prodat svůj prohlížeč Chrome ani operační systém Android. Rozhodl o tom soud ve Washingtonu, který tak zamítl požadavek amerického ministerstva spravedlnosti. Soud ale firmě nařídil sdílet data s jinými podniky v zájmu posílení konkurence v oblasti internetového vyhledávání. Zároveň Googlu zakázal uzavírat dohody s výrobci mobilních a dalších zařízení, které by znemožňovaly
… více »Prvního září ozbrojení policisté zatkli na na londýnském letišti Heathrow scénáristu a režiséra Grahama Linehana, známého především komediálními seriály Ajťáci, Otec Ted nebo Black Books. Během výslechu měl 57letý Graham nebezpečně zvýšený krevní tlak až na samou hranici mrtvice a proto byl z policejní stanice převezen do nemocnice. Důvodem zatčení bylo údajné podněcování násilí v jeho 'vtipných' příspěvcích na sociální síti
… více »Studentská dílna Macgyver zve na další Virtuální Bastlírnu - pravidelné online setkání všech, kdo mají blízko k bastlení, elektronice, IT, vědě a technice. Letní prázdniny jsou za námi a je čas probrat novinky, které se přes srpen nahromadily. Tentokrát jich je více než 50! Těšit se můžete mimo jiné na:
Hardware – Bus Pirate na ESP32, reverse engineering Raspberry Pi, pseudo-ZX-80 na RISC-V, PicoCalc, organizéry na nářadí z pěny nebo … více »Google Chrome 140 byl prohlášen za stabilní. Nejnovější stabilní verze 140.0.7339.80 přináší řadu novinek z hlediska uživatelů i vývojářů. Podrobný přehled v poznámkách k vydání. Opraveno bylo 6 bezpečnostních chyb. Vylepšeny byly také nástroje pro vývojáře.
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: