Koolikoti probleem

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 :-)

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);
}

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.

Kas keegi viitsiks üle vaadata selle? enam-vähem töötab:

sis = file("sk.in", "r")
val = file("sk.val", "wt")

M = int(sis.readline().strip()) # Seljakoti max kandev6ime
N = int(sis.readline().strip()) # Esemete arv

W, P = [], [] # Kaal, maksumused

for i in range(N):
    line = map(int, sis.readline().strip().split())
    W.append(line[0])
    P.append(line[1])

values = [0 for i in range(100)]
lisatud = [-1 for i in range(100)]
c = len(W)

for i in range(1, M + 1):
    for j in range(c):
    if (W[j] <= i) and (values[i] < values[i - W[j]] + P[j]):
        values[i] = values[i - W[j]] + P[j]
        lisatud[i] = j

for i in range(M + 1):
    if lisatud[i] != -1:
    print "Kaal %i; Maksumus %i, esemeid %i, kaaluga %i" % (i, values[i], lisatud[i] + 1, i - W[lisatud[i]])

Mi = M - 1

while Mi > 0 and lisatud[Mi] != -1:
    print "Lisatud objekt %i; kaal %i, hind %i, ruumi j2rel %i" % (lisatud[Mi], W[lisatud[i]], P[lisatud[i]], Mi - W[lisatud[Mi]])
    Mi -= W[lisatud[Mi]]