logi sisse meist KKK

hakkas siis selline probleem huvitama nagu seda on "knapsack problem", uurisin siis netist, kuidagi sain aru miskit aga nagu miskit jäi puudu kah..


<?php
$arr = array(array("weight"=>3, "val"=>4),
array("weight"=>4, "val"=>5),
array("weight"=>7, "val"=>10),
array("weight"=>8, "val"=>11),
array("weight"=>9, "val"=>13));

function knapsack_dynamical($cap)
{
   $memo = array(array("weight" => 0, "val" => 0));
   global $arr;
   $max = array("weight" => 0, "val" => 0);
   for($i = 1; $i <= $cap; $i++)
   {
       for($j = 0; $j < count($arr); $j++)
       {
           $item_v = $arr[$j]["val"];
           $item_ca = $arr[$j]["weight"];
           if($item_ca > $i)
             continue;

if(($w = $memo[$i - 1]["weight"] + $item_ca) <= $i)
             if(($t = $memo[$i - 1]["val"] + $item_v) > $max["val"])
               $max = array("weight" => $w, "val" => $t);

// Or current element is bigger 
           if($item_v > $max["val"])
              if($item_ca <= $i)
                 $max = array("weight" => $item_ca, "val" => $item_v);
       }
       echo "Best $i = {$max['val']} - current_weight{$max['weight']}\n";
       $memo[$i] = $max;
   }   
   return $memo[count($memo) - 1]["val"];
}

$memo = array(0);
function knapsack_recursive($cap)
{
  global $arr, $memo;
  if(isset($memo[$cap]))
    return $memo[$cap];

$max = 0;
  for($i = 0; $i < count($arr); $i++)
  {
     $w = $arr[$i]["weight"];
     if($w <= $cap && 
         ($t = $arr[$i]["val"] + knapsack_recursive($cap - $w)) > $max)
             $max = $t;
  }
   return $memo[$cap] = $max;
}

echo knapsack_dynamical(17) . " | recursive " . knapsack_recursive(17);
echo htmlentities(file_get_contents(__FILE__));
?>

küsimus siis selles, et dünaamiliselt töötav algorithm ei suuda leida õiget vastust 24, samas, kuulsin, et see oli NP-complete probleem seega ta ei annagi alati õiget vastust(parandage kui eksin).. samas saan aru kah miks ta ei leidnud, rekursiivse lahenduse juures ta teeb koti väiksemaks item.weight'i poolest aga dünaamilises me lihtsalt proovime kõik $cap variandid läbi(1-17)..

igaks juhuks tahtsin üle küsida, kui keegi kogenum viitsiks koodi vaadata :), äkki lihtsalt ma olen teinud dünaamilise lahenduse valesti?

ps, kuidas siia foorumisse koodi kopeerida ilma, et peaks enne htmlentitiesit kasutama :P?

küsitud Dec 22 '09 at 22:44

erti%202's gravatar image

erti 2
71347

silt muudetud Aug 03 '11 at 13:36

dig's gravatar image

dig
17415

Viimase küsimuse kohta: kasuta

 asemel treppimist nelja tühiku võrra.

(Dec 25 '09 at 22:35) Rene Saarsoo ♦♦

Seljakoti ülesande DP algoritm töötab eeldusel, et kaalud on viisakas suuruses täisarvud.

NP-täielik (raske) on ülesanne suvaliste kaalude korral. Mõlemad algoritmid nii DP kui variantide läbivaatus annavad (korrektselt realiseerituna) täpselt sama vastuse. Küsimus on lihtsalt kuluvas ajas.

Dünaamlise lahenduse ajaline keerukus on O(n * W), kus n on esemete arv ja W on maksimaalne kaal st. ideeks on igale võimalikule kogukaalule püüda liita kõiki esemeid, säilitades iga kaalu jaoks maksimaalse summa.

Oluline on tähele panna, et seljakotti pandavate asjade tüübi järgi jaguneb ülesanne omakorda kaheks: igat asja on piiramatus koguses (tehniliselt lihtsam juht) või täpselt üks (täiendavad komplikatsioonid ja mälukulu, kuid ajaline keerukus sama)

http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_solution

Koodi osas võib öelda, et kindlasti on vigane, kuna töötab valesti :-)

link

vastatud Dec 22 '09 at 23:35

sigamozart's gravatar image

sigamozart
2994

edited Dec 22 '09 at 23:43

Kuna pole aru saada, kas sigamozarti vastus oli piisav, panen igaks juhuks välja ka töötava DP lahenduse:

function knapsack_dynamical($cap) {
  global $arr;
  // map each weight we can get by combining the given items
  // to the best value we can get with exactly this weight;
  // initially, with total weight 0, we have total value 0
  $memo = array(0 => 0);
  for($i = 0; $i < count($arr); $i++) {
    // for each item, consider all total weights
    // to which this item could be added without
    // exceeding the total capability of the sack;
    // note the order, it does matter
    for($j = $cap - $arr[$i]["weight"]; $j >= 0; $j--) {
      if (isset($memo[$j])) {
        // if weight $j could be achieved with items 0..$i-1,
        // consider, what would happen if we added $i to the set
        $new_weight = $j + $arr[$i]["weight"];
        $new_val = $memo[$j] + $arr[$i]["val"];
        if (!isset($memo[$new_weight])) {
          // if this weight has not been achieved before,
          // the new result is the best for this weight so far
          $memo[$new_weight] = $new_val;
        } elseif ($memo[$new_weight] < $new_val) {
          // if previous result for this weight was less
          // the new result is the new best for this weight
          $memo[$new_weight] = $new_val;
        }
      }
    } // loop over weights
  } // loop over items
  // the answer is the maximal value in $memo; note that it is
  // not necessarily located at the maximal or last used index
  return max($memo);
}
link

vastatud Jan 01 '10 at 22:29

Ahto%20Truu's gravatar image

Ahto Truu ♦♦
6596711

Selgituseks niipalju, et iga NP((N)ondeterministic (P)olynomial time) lahendatavat probleemi ei saa lahendada P-s(deterministic (P)olynomial time). Ehk siis deterministlikult ja polünomiaalse ajaga. Probleem kuhu iga NP probleemi annab polünomiaalse ajaga algoritmiga taandada on NP-raske. Kui algoritm lahendab NP-raske probleemi, siis saab sellega ka NP probleemi lahendada. NP-raske probleem võib kuuluda ka NP klassi aga ei pea ilmtingimata.

Koolikoti ja rändkaupmehe probleemid on NP-rasked ja samas ka NP klassi kuuluvad. Selle tõttu saab mõlemat neist redutseerida polünomiaalse ajaga algoritmiga teiseks. Probleem, mis on NP-raske ja samas ka NP on NP-täielik.

Kui sa leiad polünomiaalse ajaga algoritmi NP-täieliku probleemi jaoks tähendab see automaatselt, et P ja NP klassid on võrdsed.

Põhimõtteliselt kui sa teed koolikoti probleemi jaoks algoritmi mitte-deterministlikult ja determineerid selle siis saad eksponentsiaalselt suureneva lahenduse, mida ei aita ka minimiseerimise algoritm, mis ikka jookseb polünomiaalse ajaga.

Ka on olemas optimiseerimise meetodid, mis suudavad maksimaalset vastuvõetavat N väärtust, mille korral lahenduse otsimine ei ole liiga kulukas, edasi nihutada. Need meetodid kärbivad lahenduseruumis otsimise suundade arvu. (Näiteks Branch and Bound(B&B)).

See ei tähenda, et puudub algoritm leidmaks ligilähedane lahendus.

Väga huvitav probleem igaljuhul.

link

vastatud Dec 31 '09 at 14:35

blinx's gravatar image

blinx
313

Lisaks selle selgituse juurde omakorda täpsustuse, et NP-täielik on seljakotiülesande üldine, suvaliste kaaludega variant. Mitte liiga suurte täisarvuliste kaalude korral on tegemist erijuhuga, mille lahendamiseks on teada ka efektiivsemaid algoritme kui kõigi variantide läbivaatus (näiteks dünaamiline planeerimine, kusjuures korrektselt programmeeritud DP lahendus annab täpse vastuse, mitte ligikaudse lähendi).

(Jan 01 '10 at 14:26) Ahto Truu ♦♦
Sinu vastus
lülita eelvaade

Jälgi seda küsimust

By Email:

Pärast sisselogimist saad tellida muudatuse teavitusi siit

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *kaldkiri* või __kaldkiri__
  • **paks kiri** või __paks kiri__
  • link:[tekst](http://url.com/ "pealkiri")
  • pilt?![alt tekst](/path/img.jpg "pealkiri")
  • nummerdatud nimekiri: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • põhilised HTML märgendid on samuti toetatud

Pinu tööpakkumised

kõik pakkumised »

Küsimuse sildid:

×1
×1

küsitud: Dec 22 '09 at 22:44

nähtud: 4,277 korda

viimati uuendatud: Aug 03 '11 at 13:36

Sarnased küsimused

Litsents: Creative Commons Attribution License | Kontakt: info@pinu.ee