abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 02:20 | Zajímavý článek

David Revoy, autor open source webového komiksu Pepper&Carrot nebo portrétu GNU/Linuxu, upozorňuje na svém blogu, že nový Inkscape 0.92 rozbíjí dokumenty vytvořené v předchozích verzích Inkscape. Problém by měl být vyřešen v Inkscape 0.92.2 [reddit].

Ladislav Hagara | Komentářů: 0
dnes 02:02 | Komunita

Øyvind Kolås, hlavní vývojář grafických knihoven GEGL a babl, které využívá grafický program GIMP, žádá o podporu na Patreonu. Díky ní bude moci pracovat na vývoji na plný úvazek. Milník 1000 $, který by stačil na holé přežití, se již téměř podařilo vybrat, dalším cílem je dosažení 2500 $, které mu umožní běžně fungovat ve společnosti.

xkomczax | Komentářů: 9
včera 23:54 | Pozvánky

DevConf.cz 2017, již devátý ročník jedné z největších akcí zaměřených na Linux a open source ve střední Evropě, proběhne od pátku 27. ledna do neděle 29. ledna v prostorách Fakulty informačních technologií Vysokého učení technického v Brně. Na programu je celá řada zajímavých přednášek a workshopů. Letos je povinná registrace.

Ladislav Hagara | Komentářů: 0
včera 22:11 | Nová verze

Byla vydána verze 1.0.0 emulátoru terminálu Terminology postaveného nad EFL (Enlightenment Foundation Libraries). Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
20.1. 17:00 | Nová verze

Byl vydán Docker 1.13. Přehled novinek na YouTube a v poznámkách k vydání na GitHubu. Docker umožňuje běh aplikací v softwarových kontejnerech (Wikipedia).

Ladislav Hagara | Komentářů: 4
20.1. 15:51 | Komunita

Mozilla.cz informuje, že nástroje pro webové vývojáře se možná oddělí od Firefoxu a stanou doplňkem. Nástroje pro webové vývojáře prošly velkým přepisem a tým, který se stará o jejich vývoj, by uvítal možnost jejich častějších aktualizacích nezávisle na vydávání nových verzí Firefoxu.

Ladislav Hagara | Komentářů: 8
20.1. 07:00 | Humor

Čtenářům AbcLinuxu vše nejlepší k dnešnímu Dni zvýšení povědomí o tučňácích (Penguin Awareness Day).

Ladislav Hagara | Komentářů: 0
20.1. 06:00 | Komunita

Bylo spuštěno hlasování o přednáškách a workshopech pro letošní InstallFest, jenž proběhne o víkendu 4. a 5. března v Praze. Současně byla oznámena změna místa. InstallFest se letos vrací zpět na Karlovo náměstí do budovy E.

Ladislav Hagara | Komentářů: 0
20.1. 02:48 | Komunita

Greg Kroah-Hartman potvrdil, že Linux 4.9 je jádrem s prodlouženou upstream podporou (LTS, Long Term Support). Podpora je plánována do ledna 2019. Aktuální jádra s prodlouženou podporou jsou tedy 3.2, 3.4, 3.10, 3.12, 3.16, 3.18, 4.1, 4.4 a 4.9.

Ladislav Hagara | Komentářů: 0
20.1. 00:11 | Zajímavý článek

Výrobce síťových prvků, společnost Netgear, spustila nový program, který slibuje vývojářům, expertům, ale i běžným uživatelům vyplacení finanční odměny za nalezení bezpečnostních chyby v jejich produktech. Za nalezení zranitelnosti v hardware, API nebo mobilní aplikaci nabízí odměnu od 150 do 15 tisíc dolarů (dle závažnosti).

Michal Makovec | Komentářů: 0
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (10%)
 (2%)
 (74%)
 (3%)
 (10%)
Celkem 359 hlasů
 Komentářů: 25, poslední včera 13:34
Rozcestník
Reklama
Štítky: není přiřazen žádný štítek

Dotaz: Algoritmus výpočtu

16.8.2010 11:27 Vjetnam
Algoritmus výpočtu
Přečteno: 448×
Zdravím, potřeboval bych pomoci z vytvořením optimálního algoritmu.
Zadání:
V internetovém obchode je možno zakoupit zboží v různých baleních za různou cenu.
např.

bal1 (1ks, 20kč/ks)
bal2 (5ks, 18kč/ks)
bal3 (10ks, 19kč/ks)
bal4 (50ks, 17kč/ks)

Zákazník požaduje např 78ks zboží a program by měl optimální počty balení vložit do košíku, aby to pro zázaníka bylo cenově nejvýhodnější.

Takže v tomto případě 1*bal4, 5*bal2, 3*bal1.

Napadá vás jiné řešení než zkoušet všechny možné kombinace a poté vyhodnotit která je nejvýhodnější.

Díky.

Řešení dotazu:


Odpovědi

16.8.2010 12:03 blondak | skóre: 36 | blog: Blondak | Čáslav
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
seřadit si to sestupně podle ceny za kus a pak beze zbytku dělit a zbytek zase a zase .....
78  / 50 = 1
(28)/ 5  = 5
(3) / 10 = 0
(3) / 1  = 3
(0)
Každý problém ma své logické, snadno pochopitelné nesprávné řešení.
16.8.2010 12:07 Vjetnam
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
Takto to mám uděláno teď ale ve specifických případech to nefunguje. např.
bal1 (1ks, 100kč/ks)
bal2 (7ks, 10kč/ks)
bal3 (20ks 9kč/ks)
a zákazník požaduje 21ks

dle tohoto by vyšlo 1*bal3 + 1*bal1 výsledná cena 280kč

správně by mělo být 3*bal2 výsledná cena 210kč

16.8.2010 12:24 chrono
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
Tie balenia máš zoradené naopak (najskôr máš hľadať najväčšie balenia).
16.8.2010 12:27 Vjetnam
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
To samozřejmě ano. ale podle navrhovaného způsobu celočíselného dělení to fungovat v tomto případě prostě nebude.
ava avatar 16.8.2010 12:10 ava | skóre: 10
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
Press any key to continue, or any other key to cancel
16.8.2010 12:55 Vjetnam
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
Díky za nasměrování. To je přesně ten můj problém. I když nejsem zrovna happy že to není triviální :-/
22.8.2010 22:38 Vladimír Čunát | skóre: 18
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
NP-úplnost nemusí být až tak velká překážka. Třeba pro batoh zrovna existuje jednoduchý pseudopolynomiální algoritmus. Dá se najít třeba na http://en.wikipedia.org/wiki/Knapsack_problem v sekci "Dynamic programming solution". IMO je to pro zadání jako v příkladu velmi dobře použitelný algoritmus - je jednoduchý a rozhodně lepší než zkoušení všech možností.
16.8.2010 12:16 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
Princip: znám-li nejnižší cenu pro 1 až n kusů, pak mohu spočítat i nejnižší cenu pro n+1 kusů. Detaily pak závisí na tom, jestli dovolíte nakoupit i více kusů, než je požadováno (bude-li cena nižší).
16.8.2010 12:29 Vjetnam
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
Cíl je aby zákazník dostal do košíku přesný počet kusů který požadoval. Takže ne.
16.8.2010 13:03 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
K je požadovaný počet kusů. Na vstupu jsou dvojice (počet kusů v balení, cena balení).

Inicializace: Udělám pole arr indexované čísly 1..K, kde i-tý prvek pole je roven nejnižší ceně za balení s i kusy, pokud takové balení neexistuje, je tam nekonečno.

n-tý krok algoritmu: Prvky 1..n-1 se už nezmění a obsahují optimální cenu za dané počty kusů. Nyní spočítáme optimální cenu za n kusů. M je minimum hodnot arr[i] + arr[n-i] přes všechna i=1..n-1. Nejnižší cena za n kusů je arr[n] <- min(M, arr[n]).
wamba avatar 16.8.2010 13:14 wamba | skóre: 37 | blog: wamba
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
přes všechna i=1..n-1
stačí přes všechna i=1..(n-1 div 2) jestli se nepletu
This would have been so hard to fix when you don't know that there is in fact an easy fix.
16.8.2010 15:32 Vjetnam
Rozbalit Rozbalit vše Re: Algoritmus výpočtu
Pro zajímavost zde je výpočet který používám.
class Variation {
	var $pieces_arr=array();
	var $prices_arr=array();
	var $sum_count=0;
	var $sum_price=0;
	
	function Variation() {

	}
	
	function setPieces($type, $count, $price){
		$this->pieces_arr[$type] = $count;
		$this->prices_arr[$type] = $count*$price;
		$this->sum_count = array_sum($this->pieces_arr);
		$this->sum_price = array_sum($this->prices_arr);
	}
}

class VariationSolver {
	var $itemsArr = array();
	var $reqCount = 0;
	var $BestVar;
	
	function VariationSolver() {
		$this->BestVar = null;
	}
	
	function setRequestedCount($count){
		$this->reqCount = $count;
	}
	
	function addVariationItem($type, $piece, $price){
		$this->itemsArr[] = array($type, $piece, $price);
	}
	
	function compute($level, $VarObj){
		$max_level = sizeof($this->itemsArr)-1;
		$increment = $this->itemsArr[$level][1];
		for ($i = 0; $i==0 || ($i <= $this->reqCount && ($VarObj->sum_count+$increment)<=$this->reqCount) ; $i=$i+$increment) {
			$VarObj->setPieces($this->itemsArr[$level][0], $i, $this->itemsArr[$level][2]);
			
			if ($max_level>$level){
				$this->compute($level+1, $VarObj);
			}
			else {
				if ($VarObj->sum_count==$this->reqCount){
					if ($this->BestVar == null || $VarObj->sum_price < $this->BestVar->sum_price){
						$this->BestVar = $VarObj;
					}
				}
			}
		}
	}
	
	function getBestVar(){ //slow
		$this->BestVar = null;
		if (sizeof($this->itemsArr)>0){
			$this->compute(0, new Variation());
		}
		return $this->BestVar;
	}
}

//==== Vypocet ====
$VS = new VariationSolver();
$VS->setRequestedCount(100);
$VS->addVariationItem("N",1,100);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("B",2,95);     // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("A1",5,90);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("D",10,98);    // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("IC1",20,81);  // typ baleni, pocet kusu v baleni, cena za kus
$VS->addVariationItem("IC2",50,80);  // typ baleni, pocet kusu v baleni, cena za kus

print_r( $VS->getBestVar() );

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.