आइटम समूह के साथ Knapsack समीकरण

Question

स्पष्ट रूप से स्टैक ओवरफ़्लो पर कोई समस्या नहीं कह सकता है, हालांकि मैं वर्तमान में यह समझने की कोशिश कर रहा हूं कि Knapsack समस्या के भीतर आइटम समूहों के रूप में बाधाओं को कैसे एकीकृत किया जाए। मेरे गणित कौशल इस परिस्थिति में काफी सीमित साबित हो रहे हैं, हालांकि मैं इस काम को इरादे के साथ-साथ यह समझने के लिए बहुत प्रेरित हूं कि प्रत्येक पहलू क्या करता है (उस क्रम में जब चीजें काम करते हैं तो चीजों को और अधिक समझ में आता है)।

इसके साथ, मुझे Rosetta Code पर एक बिल्कुल सुंदर कार्यान्वयन मिला है और कुछ मूलभूत परिप्रेक्ष्य से इसे बेहतर ढंग से समझने में मेरी मदद करने के लिए कुछ परिवर्तनीय नामों को साफ़ किया गया है।

दुर्भाग्यवश मुझे यह पता लगाने में एक अविश्वसनीय मुश्किल समय है कि मैं आइटम समूह को शामिल करने के लिए इस तर्क को कैसे लागू कर सकता हूं। मेरा उद्देश्य फंतासी टीमों के निर्माण के लिए है, मेरा खुद का मूल्य & प्रति खिलाड़ी वजन (अंक/वेतन) की आपूर्ति करना, लेकिन समूह के बिना (मेरे मामले में स्थितियां) मैं ऐसा करने में असमर्थ हूं।

क्या कोई मुझे इस के लिए सही दिशा में इंगित करने में सक्षम होगा? मैं अन्य भाषाओं से कोड उदाहरणों की समीक्षा कर रहा हूं और पूरी तरह से समस्या के अतिरिक्त विवरणों की समीक्षा कर रहा हूं, हालांकि मैं संभवतः किसी भी माध्यम से लागू समूहों को प्राप्त करना चाहता हूं।

<?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

वह knapsack प्रोग्राम पारंपरिक है, लेकिन मुझे लगता है कि यह क्या हो रहा है यह अस्पष्ट करता है। मैं आपको दिखाता हूं कि डीपी को ब्रूट फोर्स सॉल्यूशन से अधिक सरलता से कैसे प्राप्त किया जा सकता है।

पायथन में (क्षमा करें; यह मेरी पसंद की स्क्रिप्टिंग भाषा है), एक ब्रूट फोर्स समाधान इस तरह दिख सकता है। सबसे पहले, चौड़ाई-पहली खोज के साथ सभी सबसेट बनाने के लिए एक फ़ंक्शन है (यह महत्वपूर्ण है)।

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 

तो फिर वहाँ एक समारोह है कि True लौटाता है यदि समाधान मान्य है (बजट के भीतर है और एक उचित स्थिति टूटने के साथ) है - यह is_valid_solution कहते हैं - और एक समारोह है कि, एक समाधान दिया, रिटर्न की कुल खिलाड़ी मूल्य (total_player_value)। यह मानते हुए कि players उपलब्ध खिलाड़ियों की सूची है, इष्टतम समाधान यह है।

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

अब, एक डी पी के लिए, हम एक समारोह cullall_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 

क्या cull करता आंशिक समाधान है कि स्पष्ट रूप से एक इष्टतम समाधान के लिए हमारी खोज में याद किया नहीं जा रहे फेंक है। यदि आंशिक समाधान पहले से ही बजट से अधिक है, या यदि पहले से ही एक ही स्थिति में बहुत से खिलाड़ी हैं, तो इसे सुरक्षित रूप से त्याग दिया जा सकता है। is_valid_partial_solution एक ऐसा फ़ंक्शन बनें जो इन शर्तों का परीक्षण करता है (यह शायद is_valid_solution जैसा दिखता है)। अब तक हमारे पास यह है।

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

अन्य महत्वपूर्ण परीक्षण यह है कि कुछ आंशिक समाधान दूसरों की तुलना में बेहतर हैं। यदि दो आंशिक समाधानों में एक ही स्थिति टूटना होता है (उदाहरण के लिए, दो आगे और एक केंद्र) और इसकी लागत होती है, तो हमें केवल अधिक मूल्यवान रखने की आवश्यकता होती है। cost_and_position_breakdown एक समाधान लें और एक स्ट्रिंग का उत्पादन करें जो निर्दिष्ट विशेषताओं को एन्कोड करता है।

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

यही है। यहां बहुत सारे अनुकूलन किए जाने हैं (उदा।, आंशिक समाधानों को फेंक दें जिसके लिए एक सस्ता और अधिक मूल्यवान आंशिक समाधान है; डेटा संरचनाओं को संशोधित करें ताकि हम हमेशा स्क्रैच से मूल्य और स्थिति टूटने की गणना नहीं कर रहे हैं और भंडारण लागत को कम करने के लिए), लेकिन इसे लगातार बढ़ाया जा सकता है।

Answer 2

एक PHP में पुनरावर्ती कार्यों रचना के संबंध में संभावित छोटे लाभ यह है कि चर मूल्य द्वारा पारित कर रहे हैं (जिसका अर्थ है एक प्रति किया जाता है) के बजाय संदर्भ है, जो एक या दो कदम बचा सकता है की तुलना में है।

शायद आप नमूना इनपुट और आउटपुट सहित जो भी खोज रहे हैं उसे बेहतर ढंग से स्पष्ट कर सकते हैं। यहां एक उदाहरण दिया गया है जो दिए गए समूहों से संयोजन बनाता है - मुझे यकीन नहीं है कि यह आपका इरादा है ... मैंने आंशिक परिणाम तक पहुंचने वाले अनुभाग को कम मूल्य वाले संयोजनों को अनुमति दी है, यदि उनके वजन कम हैं - इन सभी को बदला जा सकता है विशिष्ट तरीकों से छुटकारा पाने के लिए जो आप चाहें।

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

आउटपुट:

$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]] 
*/