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 13:55 | Nová verze

    Byla vydána nová verze 5.18 živé linuxové distribuce Tails (The Amnesic Incognito Live System), jež klade důraz na ochranu soukromí uživatelů a anonymitu. Přehled změn v příslušném seznamu. Tor Browser byl povýšen na verzi 12.5.6. Tor na verzi 0.4.8.6.

    Ladislav Hagara | Komentářů: 0
    dnes 10:55 | Nová verze

    Šifrovací nástroj VeraCrypt v menším vydání 1.26.7 nejen opravuje chyby a aktualizuje podporované algoritmy (podrobnosti v poznámkách vydání), ale také přestává podporovat původní svazky TrueCrypt.

    Fluttershy, yay! | Komentářů: 0
    dnes 09:00 | Pozvánky

    V sobotu 7. října proběhne Maker Faire Liberec, festival plný workshopů, interaktivních činností a především nadšených a zvídavých lidí.

    Ladislav Hagara | Komentářů: 0
    dnes 08:00 | Zajímavý článek Ladislav Hagara | Komentářů: 0
    včera 23:44 | Komunita

    Ubuntu Summit 2023 proběhne od 3. do 5. listopadu v Rize.

    Ladislav Hagara | Komentářů: 0
    včera 19:33 | Nová verze

    Programovací jazyk Python byl vydán v nové major verzi 3.12.0. Podrobný přehled novinek v Changelogu.

    Ladislav Hagara | Komentářů: 0
    včera 17:00 | Zajímavý projekt

    Linux ve Scratchi. Ne Linux v linuxové distribuci Linux From Scratch, ale Linux bežící v emulátoru procesoru RISC-V ve vizuálním programovacím jazyce Scratch.

    Ladislav Hagara | Komentářů: 0
    včera 16:22 | Pozvánky

    Dnes ve 12 hodin začal další ročník CTF (Capture the Flag) soutěže The Catch: "Tentokrát nás kolegové z Forenzní laboratoře zavedou na loď plnou sofistikovaných síťových technologiích, kde soutěžící budou muset zvládnout náročné úkoly. Loď nese jméno našeho skvělého kolegy Josefa Vericha – síťového guru. Tradičně se soutěž koná v říjnu – měsíci kybernetické bezpečnosti."

    Ladislav Hagara | Komentářů: 1
    včera 07:00 | Pozvánky

    Konference LinuxDays 2023 proběhne již tento víkend 7. a 8. října v prostorách Fakulty informačních technologií Českého vysokého učení v Praze (FIT ČVUT). Na programu je spousta zajímavých přednášek a workshopů.

    Ladislav Hagara | Komentářů: 1
    1.10. 22:33 | IT novinky

    Netflix v pátek 29. září odeslal poslední film na DVD (YouTube). Společnost dnes známá jako streamovací služba začala před 25 lety jako půjčovna filmů na DVD. Zákazník si DVD objednal na webových stránkách, odesláno mu ale bylo klasickou poštou. Po zhlédnutí jej vložil do obálky a poslal zpět.

    Ladislav Hagara | Komentářů: 16
    Raději
     (54%)
     (46%)
    Celkem 41 hlasů
     Komentářů: 3, poslední včera 23:31
    Rozcestník
    Š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: 466×
    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: 19
    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: 38 | 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.