Equazione dello zaino con gruppi di articoli

Question

Apparentemente non si può chiamare un problema su Stack Overflow, tuttavia attualmente sto cercando di capire come integrare i vincoli sotto forma di gruppi di articoli all'interno del problema dello zaino. Le mie capacità matematiche si stanno dimostrando piuttosto limitanti in questa situazione, tuttavia sono molto motivato sia a fare questo lavoro come previsto, sia a capire cosa fa ogni aspetto (nell'ordine dato che le cose hanno più senso quando lavorano).

Detto questo, ho trovato un'implementazione assolutamente splendida al Rosetta Code e ho pulito alcuni nomi delle variabili per aiutarmi a capire meglio da una prospettiva molto semplice.

Sfortunatamente sto avendo un tempo incredibilmente difficile capire come posso applicare questa logica per includere gruppi di articoli. Il mio scopo è costruire team fantasy, fornendo il mio valore & di peso (punti/salario) per giocatore ma senza gruppi (posizioni nel mio caso) non sono in grado di farlo.

Qualcuno potrebbe indicarmi la giusta direzione? Sto rivedendo esempi di codice da altre lingue e descrizioni aggiuntive del problema nel suo complesso, tuttavia vorrei mettere in atto i gruppi con qualsiasi mezzo possibile.

<?php 

function knapSolveFast2($itemWeight, $itemValue, $i, $availWeight, &$memoItems, &$pickedItems) 
{ 
    global $numcalls; 
    $numcalls++; 

    // Return memo if we have one 
    if (isset($memoItems[$i][$availWeight])) 
    { 
     return array($memoItems[$i][$availWeight], $memoItems['picked'][$i][$availWeight]); 
    } 
    else 
    { 
     // At end of decision branch 
     if ($i == 0) 
     { 
      if ($itemWeight[$i] <= $availWeight) 
      { // Will this item fit? 
       $memoItems[$i][$availWeight] = $itemValue[$i]; // Memo this item 
       $memoItems['picked'][$i][$availWeight] = array($i); // and the picked item 
       return array($itemValue[$i],array($i)); // Return the value of this item and add it to the picked list 

      } 
      else 
      { 
       // Won't fit 
       $memoItems[$i][$availWeight] = 0; // Memo zero 
       $memoItems['picked'][$i][$availWeight] = array(); // and a blank array entry... 
       return array(0,array()); // Return nothing 
      } 
     } 

     // Not at end of decision branch.. 
     // Get the result of the next branch (without this one) 
     list ($without_i,$without_PI) = knapSolveFast2($itemWeight, $itemValue, $i-1, $availWeight,$memoItems,$pickedItems); 

     if ($itemWeight[$i] > $availWeight) 
     { // Does it return too many? 
      $memoItems[$i][$availWeight] = $without_i; // Memo without including this one 
      $memoItems['picked'][$i][$availWeight] = array(); // and a blank array entry... 
      return array($without_i,array()); // and return it 
     } 
     else 
     { 
      // Get the result of the next branch (WITH this one picked, so available weight is reduced) 
      list ($with_i,$with_PI) = knapSolveFast2($itemWeight, $itemValue, ($i-1), ($availWeight - $itemWeight[$i]),$memoItems,$pickedItems); 
      $with_i += $itemValue[$i]; // ..and add the value of this one.. 

      // Get the greater of WITH or WITHOUT 
      if ($with_i > $without_i) 
      { 
       $res = $with_i; 
       $picked = $with_PI; 
       array_push($picked,$i); 
      } 
      else 
      { 
       $res = $without_i; 
       $picked = $without_PI; 
      } 

      $memoItems[$i][$availWeight] = $res; // Store it in the memo 
      $memoItems['picked'][$i][$availWeight] = $picked; // and store the picked item 
      return array ($res,$picked); // and then return it 
     } 
    } 
} 

$items = array("map","compass","water","sandwich","glucose","tin","banana","apple","cheese","beer","suntan cream","camera","t-shirt","trousers","umbrella","waterproof trousers","waterproof overclothes","note-case","sunglasses","towel","socks","book"); 
$weight = array(9,13,153,50,15,68,27,39,23,52,11,32,24,48,73,42,43,22,7,18,4,30); 
$value = array(150,35,200,160,60,45,60,40,30,10,70,30,15,10,40,70,75,80,20,12,50,10); 

## Initialize 
$numcalls = 0; 
$memoItems = array(); 
$selectedItems = array(); 

## Solve 
list ($m4, $selectedItems) = knapSolveFast2($weight, $value, sizeof($value)-1, 400, $memoItems, $selectedItems); 

# Display Result 
echo "<b>Items:</b><br>" . join(", ", $items) . "<br>"; 
echo "<b>Max Value Found:</b><br>$m4 (in $numcalls calls)<br>"; 
echo "<b>Array Indices:</b><br>". join(",", $selectedItems) . "<br>"; 

echo "<b>Chosen Items:</b><br>"; 
echo "<table border cellspacing=0>"; 
echo "<tr><td>Item</td><td>Value</td><td>Weight</td></tr>"; 

$totalValue = 0; 
$totalWeight = 0; 

foreach($selectedItems as $key) 
{ 
    $totalValue += $value[$key]; 
    $totalWeight += $weight[$key]; 

    echo "<tr><td>" . $items[$key] . "</td><td>" . $value[$key] . "</td><td>".$weight[$key] . "</td></tr>"; 
} 

echo "<tr><td align=right><b>Totals</b></td><td>$totalValue</td><td>$totalWeight</td></tr>"; 
echo "</table><hr>"; 

?> 

Answer 1

Quel programma di zaino è tradizionale, ma penso che oscuri quello che sta succedendo. Lasciate che vi mostri come il DP può essere derivato più direttamente da una soluzione di forza bruta.

In Python (mi dispiace, questo è il mio linguaggio di scripting preferito), una soluzione di forza bruta potrebbe apparire come questa. Innanzitutto, c'è una funzione per generare tutti i sottoinsiemi con ricerca in ampiezza (questo è importante).

def all_subsets(S): # brute force 
    subsets_so_far = [()] 
    for x in S: 
     new_subsets = [subset + (x,) for subset in subsets_so_far] 
     subsets_so_far.extend(new_subsets) 
    return subsets_so_far 

Poi c'è una funzione che restituisce True se la soluzione è valida (nel budget e con una corretta ripartizione posizione) - chiamano is_valid_solution - e una funzione che, data una soluzione, restituisce il valore totale giocatore (total_player_value). Supponendo che players sia la lista dei giocatori disponibili, la soluzione ottimale è questa.

max(filter(is_valid_solution, all_subsets(players)), key=total_player_value) 

Ora, per un DP, aggiungiamo una funzione cull-all_subsets.

def best_subsets(S): # DP 
    subsets_so_far = [()] 
    for x in S: 
     new_subsets = [subset + (x,) for subset in subsets_so_far] 
     subsets_so_far.extend(new_subsets) 
     subsets_so_far = cull(subsets_so_far) ### This is new. 
    return subsets_so_far 

Cosa cull fa è quello di buttare via le soluzioni parziali che non sono chiaramente andando a perdere nella nostra ricerca di una soluzione ottimale. Se la soluzione parziale è già al di sopra del budget, o se ha già troppi giocatori in una posizione, allora può essere scartata tranquillamente. Lascia che is_valid_partial_solution sia una funzione che verifica queste condizioni (probabilmente assomiglia molto a is_valid_solution). Finora abbiamo questo.

def cull(subsets): # INCOMPLETE! 
    return filter(is_valid_partial_solution, subsets) 

L'altro test importante è che alcune soluzioni parziali sono solo migliori di altre. Se due soluzioni parziali hanno la stessa interruzione di posizione (ad es. Due avanti e un centro) e costano allo stesso modo, dobbiamo solo mantenere quella più preziosa. Lasciare cost_and_position_breakdown prendere una soluzione e produrre una stringa che codifica gli attributi specificati.

def cull(subsets): 
    best_subset = {} # empty dictionary/map 
    for subset in filter(is_valid_partial_solution, subsets): 
     key = cost_and_position_breakdown(subset) 
     if (key not in best_subset or 
      total_value(subset) > total_value(best_subset[key])): 
      best_subset[key] = subset 
    return best_subset.values() 

Questo è tutto. C'è un sacco di ottimizzazione da fare qui (ad es.buttare via soluzioni parziali per le quali esiste una soluzione parziale più economica e più preziosa; modificare le strutture dei dati in modo da non calcolare sempre il valore e la ripartizione della posizione da zero e ridurre i costi di archiviazione), ma può essere affrontato in modo incrementale.

Answer 2

Un potenziale piccolo vantaggio per quanto riguarda la composizione di funzioni ricorsive in PHP è che le variabili vengono passate per valore (ovvero viene eseguita una copia) anziché per riferimento, che può salvare un passo o due.

Forse potresti chiarire meglio cosa stai cercando includendo un esempio di input e output. Ecco un esempio che crea combinazioni da gruppi dati - Non sono sicuro che sia questa la tua intenzione ... Ho fatto in modo che la sezione che accede al risultato parziale consenta di considerare combinazioni con meno valore se il loro peso è inferiore - tutto questo può essere cambiato per potare i modi specifici che desideri.

function make_teams($players, $position_limits, $weights, $values, $max_weight){ 
    $player_counts = array_map(function($x){ 
        return count($x); 
        }, $players); 
    $positions = array_map(function($x){ 
       $positions[] = []; 
       },$position_limits); 
    $num_positions = count($positions); 
    $combinations = []; 
    $hash = []; 
    $stack = [[$positions,0,0,0,0,0]]; 

    while (!empty($stack)){ 
    $params = array_pop($stack); 
    $positions = $params[0]; 
    $i = $params[1]; 
    $j = $params[2]; 
    $len = $params[3]; 
    $weight = $params[4]; 
    $value = $params[5]; 

    // too heavy 
    if ($weight > $max_weight){ 
     continue; 

    // the variable, $positions, is accumulating so you can access the partial result 
    } else if ($j == 0 && $i > 0){ 

     // remember weight and value after each position is chosen 
     if (!isset($hash[$i])){ 
     $hash[$i] = [$weight,$value]; 

     // end thread if current value is lower for similar weight 
     } else if ($weight >= $hash[$i][0] && $value < $hash[$i][1]){ 
     continue; 

     // remember better weight and value 
     } else if ($weight <= $hash[$i][0] && $value > $hash[$i][1]){ 
     $hash[$i] = [$weight,$value]; 
     } 
    } 

    // all positions have been filled 
    if ($i == $num_positions){ 
     $positions[] = $weight; 
     $positions[] = $value; 

     if (!empty($combinations)){ 
     $last = &$combinations[count($combinations) - 1]; 
     if ($weight < $last[$num_positions] && $value > $last[$num_positions + 1]){ 
      $last = $positions; 
     } else { 
      $combinations[] = $positions; 
     } 
     } else { 
     $combinations[] = $positions; 
     } 

    // current position is filled 
    } else if (count($positions[$i]) == $position_limits[$i]){ 
     $stack[] = [$positions,$i + 1,0,$len,$weight,$value]; 

    // otherwise create two new threads: one with player $j added to 
    // position $i, the other thread skipping player $j 
    } else { 
     if ($j < $player_counts[$i] - 1){ 
     $stack[] = [$positions,$i,$j + 1,$len,$weight,$value]; 
     } 
     if ($j < $player_counts[$i]){ 
     $positions[$i][] = $players[$i][$j]; 
     $stack[] = [$positions,$i,$j + 1,$len + 1 
        ,$weight + $weights[$i][$j],$value + $values[$i][$j]]; 
     } 
    } 
    } 
    return $combinations; 
} 

uscita:

$players = [[1,2],[3,4,5],[6,7]]; 
$position_limits = [1,2,1]; 
$weights = [[2000000,1000000],[10000000,1000500,12000000],[5000000,1234567]]; 
$values = [[33,5],[78,23,10],[11,101]]; 
$max_weight = 20000000; 

echo json_encode(make_teams($players, $position_limits, $weights, $values, $max_weight)); 

/* 
[[[1],[3,4],[7],14235067,235],[[2],[3,4],[7],13235067,207]] 
*/