Advertisement
tnewhook

PHP Knapsack v2

Feb 16th, 2014
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2.         //Unbounded knapsack problem
  3.         //still need to figure out how many of each size
  4.          
  5.         //<?php
  6.         $w=array(1,2,3,4);
  7.         $v=array(1,2.2,3.3,4.4);
  8.         $itemCount=array();
  9.         for($i=0;$i<count($v);$i++){
  10.             $itemCount[]=0;
  11.         };
  12.         $C=16;//max weight limit of knapsack
  13.          
  14.         echo 'Knapsack is: '.Knapsack($v,$w,$C,$itemCount);
  15.          
  16.             //(N = # different items)
  17.          
  18.         function Knapsack($v,$w,$C,$itemCount){
  19.                $sol=array();
  20.                    $mySol=array();
  21.                    $myFinalSol=array();
  22.                    $N=count($v);
  23.                /* ***************************************
  24.                   Base case
  25.                   *************************************** */
  26.                         if ($C == 0 )
  27.                 return 0;
  28.          
  29.          
  30.                /* ==============================================
  31.                   Divide and conquer procedure
  32.                   ============================================== */
  33.          
  34.                /* ---------------------------------------
  35.                   Solve the appropriate smaller problems
  36.                   --------------------------------------- */
  37.                         for ($i=0;$i<$N;$i++){
  38.                             echo 'ORIGINAL Knapsack I: '.$i.
  39.                                 if($C>=$w[$i]){
  40.                                 $GLOBALS["itemCount"][$i]+=1;
  41.                                             echo ' GLOBALS itemCount['.$i.']='.$GLOBALS["itemCount"][$i].' i='.$i."\n";
  42.                                     //echo 'capacity('.$C.')>w[i]('.$w[$i].')<br />';
  43.                                         $sol[$i] = Knapsack($v,$w,$C-$w[$i],$GLOBALS["itemCount"]);// Knapsack capacity reduced by w[i]    
  44.                                             echo ' for loop 1 '."\n".'i: '.$i.' $sol[$i]: '.$sol[$i]."\n\n";
  45.                                 }                                                               // because it has item i packed in
  46.                                                                                                 // it already  
  47.                                 else{$sol[$i] = 0;}        // Not enough space to  pack item i
  48.                         }
  49.      
  50.         //var_dump($sol);
  51.      
  52.                /* ---------------------------------------------
  53.                   Use the solutions to the smaller problems
  54.                   to solve original problem
  55.                   --------------------------------------------- */
  56.                         for($i=0;$i<$N;$i++){
  57.                                 if($C>=$w[$i]){
  58.                                            
  59.                                         $mySol[$i]=$sol[$i]+$v[$i]; // Value is increased by v[i]
  60.                                     echo ' for loop 2 '."\n".'i: '.$i.' $mySol[$i]: '.$mySol[$i]."\n\n<br />";
  61.                                     echo '<strong> TO ADD V[i]'.$v[$i].'</strong><br />';
  62.                                 }                                                               // because it has item i packed in
  63.                                                                                                 // it already
  64.                                 else{$mySol[$i]=0;}        // Not enough space to  pack item i
  65.                }
  66.          
  67.                /* *************************
  68.                   Find the best (maximum)
  69.                   ************************* */
  70.                         $myFinalSol = $mySol[1];
  71.                         for($i=1;$i<$N;$i++){
  72.                   if($mySol[$i]>$myFinalSol){
  73.                                 $myFinalSol = $mySol[$i];}
  74.                         }
  75.                         return $myFinalSol;
  76.            };
  77.         //?>
  78.      
  79.      
  80.     ?>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement