Problém batohu

Problém batohu (0-1 knapsack problem) je úloha kombinatorické optimalizace, jejímž cílem je umístění podmnožiny předmětů (předmět má specifikován svoji cenu a váhu) do přepravky omezené kapacity (nosnosti) tak, aby cena nákladu byla maximální. Předměty nelze dělit – buď jsou v přepravce umístěny celé, nebo zde nejsou vůbec. Rozhodovací NP-úplná varianta problému řeší otázku, zda-li lze do batohu dané kapacity umístit podmnožinu daných předmětů tak, aby byl součet cen těchto předmětů alespoň k.

Formulace pomocí lineárního programování

Pomocí celočíselného lineárního programování lze problém batohu formulovat jako:

$\\max \\sum_{i \\in I} x_{i} \\cdot c_{i}$
Za podmínek:
$\\sum_{i \\in I} x_{i} \\cdot w_{i} \\leq W$
$x_{i} \\in \\{0, 1\\}$

Pseudopolynomiální algoritmus

Problém batohu lze řešit pomocí dynamického programování v pseudopolynomiálním čase. Algoritmus funguje na bázi vyplňování tabulky. Její sloupce značí cenu doposud naloženého nákladu, řádky značí stav po naložení n-té položky, buňky označují váhu nákladu.

Základní stav

Algoritmus je v prvním kroku v buňce [0, 0] , což znamená, že byla zpracována nultá položka (tj. nebyla ještě zpracována žádná položka) a cena nákladu je proto 0 (obsah buňky). Algoritmus nyní zpracuje první položku (posun na další řádek tabulky).

Krok algoritmu

Mohou nastat dvě situace – dojde proto k rozdělení řešení a algoritmus bude postupovat po obou větvích. První možností je, že algoritmus do batohu přidá danou položku a přejde na souřadnici $[y+1, x + cena\\;předmětu]$ , kde x je dosavadní součet cen položek obsažených v batohu a nastaví hodnotu pole na $z + váha\\;předmětu$ (z je dosavadní součet vah všech předmětů obsažených v batohu). Druhou možností je, že předmět do batohu nebude přidán – algoritmus přejde na souřadnici [y+1, x] , kde hodnotu pole stanoví opět jako součet vah všech obsažených předmětů (protože nebyl přidán žádný předmět, tak hodnotu pouze opíše ze zdrojového pole). Stejným způsobem algoritmus postupuje pro všechny dosažené buňky v následujícím řádku, dokud nejsou zpracovány všechny předměty (vyplněny všechny řádky).

Kolize a nepřípustné řešení

Pokud dojde ke kolizi – algoritmus se dostane do situace, kdy se do dané buňky může dostat více cestami, tak dostane přednost to řešení, jehož váha nákladu je nižší. Pokud váha nákladu překročí kapacitu batohu, tak v dané větvi nemá smysl pokračovat, protože řešení je nepřípustné.

Složitost algoritmu

Algoritmus je pseudopolynomiální, přesněji má složitost $O(C \\cdot n)$ , což znamená, že lze jeho složitost omezit polynomem vzhledem k délce vstupu ( je počet předmětů), ale nikoliv vzhledem k velikosti vstupu ( může být až exponenciálně velké).

Příklad

Mějme batoh o kapacitě 8 a předměty, jejichž váhy jsou [3,6,4,1] , tyto předměty mají hodnotu [3, 5, 3, 1] . Umístěte předměty do batohu tak, aby součet jejich cen byl maximální. Jako horní mez ceny použijte součet ceny všech předmětů.

Do batohu lze naložit předměty o ceně 7 a celkové váze 8.

Kód

Ruby


#
# Knapsack solver that uses dynamic programming approach with decomposition
# by the knapsack's capacity. Algorithm always finds the optimal solution.
#
# Author: Jakub Jirutka <jakub@jirutka.cz>
#
class CapacityDynamicSolver

  def solve(things, capacity)
    solutions = solve_subsets(things, capacity)
    bitmask = find_best_config(solutions, things)
    cost = find_best_cost(solutions)

    [bitmask, cost]
  end

private

  def solve_subsets(things, max_capacity)
    # matrix with best costs for things subset size x capacity
    solutions = Array.new(things.count+1) { Array.new(max_capacity+1) }
    solutions[0].fill(0)

    (1.. things.count).each do |items|
      thing = things[items-1]           # things are 0-based!
      prev_bests = solutions[items-1]    # best costs for various capacities

      (0.. max_capacity).each do |capacity|
        # knapsack's cost with this thing instead of some previous
        cost_with = prev_bests[capacity - thing.weight] + thing.price
        # knapsack's cost without this thing
        cost_without = prev_bests[capacity]

        # is it worth to replace last thing with this... and can we?
        solutions[items][capacity] =
          if cost_with > cost_without && thing.weight <= capacity
            cost_with
          else
            cost_without
          end
      end
    end

    solutions
  end

  def find_best_config(solutions, things)
    bitmask = Array.new(things.count, false)
    items = things.count
    capacity = solutions.last.size - 1

    while items > 0 && capacity > 0 do
      if solutions[items][capacity] != solutions[items-1][capacity]
        bitmask[items-1] = true
        capacity -= things[items-1].weight
      end
      items -= 1
    end

    bitmask
  end

  def find_best_cost(solutions)
    solutions.last.max
  end

end

class Thing
  attr_reader :id, :price, :weight

  def initialize(id, price, weight)
    @id = id
    @price = price
    @weight = weight
  end

  def to_s
    "Thing {id: #{id}, price: #{price}, weight: #{weight}}"
  end
end


#####  M a i n  #####

things = Array.new(20) {|i| Thing.new(i, rand(1..100), rand(10..200)) }
capacity = 250

config, cost = CapacityDynamicSolver.new.solve(things, capacity)

puts things
puts "Optimal configuration is: #{config.map{|used| used ? 1 : 0 }.join}, with cost: #{cost}"

Literatura

HANZÁLEK, Zdeněk. Kombinatorická optimalice - slides k přednáškám.