Online PHP editor | rfc for kF43n

<?php //Unbounded knapsack problem //still need to figure out how many of each size $w=array(2,4,6); $w = array_map("round", $w);//$w needs to be integers, $v can be floats $v=array(2.2,4.6,6.8); $C=10;//max weight limit of knapsack $itemCount=array(); for($i=0;$i<count($C);$i++){ $itemCount[$i]=0; }; $knapsackResult=Knapsack($v,$w,$C); echo 'Knapsack is: '.$knapsackResult; echo '<pre>'; var_dump($itemCount); echo '</pre>'; echo 'elements are: <pre>'; $knapsackContentsResult=KnapsackContents($knapsackResult,$itemCount,$w,$v,$C); var_dump($knapsackContentsResult); echo '</pre>'; //(N = # different items) function Knapsack($v,$w,$C){ $sol=array(); $mySol=array(); $myFinalSol=array(); $N=count($v); /**************************************** Base case *************************************** */ if ($C == 0 ) return 0; /* ============================================== Divide and conquer procedure ============================================== */ /* --------------------------------------- Solve the appropriate smaller problems --------------------------------------- */ for ($i=0;$i<$N;$i++){ if($C>=$w[$i]){ $sol[$i] = Knapsack($v,$w,$C-$w[$i]);// Knapsack capacity reduced by w[i] } // because it has item i packed in else{$sol[$i] = 0;} // Not enough space to pack item i } /* --------------------------------------------- Use the solutions to the smaller problems to solve original problem --------------------------------------------- */ for($i=0;$i<$N;$i++){ if($C>=$w[$i]){ $mySol[$i]=$sol[$i]+$v[$i]; // Value is increased by v[i] } // because it has item i packed in // it already else{$mySol[$i]=0;} // Not enough space to pack item i } /* ************************* Find the best (maximum) ************************* */ $myFinalSol = $mySol[1]; for($i=0;$i<$N;$i++){ if($mySol[$i]>$myFinalSol){ $myFinalSol = $mySol[$i]; } } $GLOBALS["itemCount"][$C]=$myFinalSol; return $myFinalSol; }; function KnapsackContents($total,$itemCount,$w,$v,$C){ //$total is the total value that the knapsack function found //$itemCount is the value at each size of the knapsack $knapsackHolds=array(); $knapsackHoldsValue=array(); end($itemCount); $placeholder=key($itemCount);//get final key in array $v=array_reverse($v);//set value & weight to prefer largest $w=array_reverse($w); while($placeholder>0){ for($j=0;$j<count($v);$j++){ if($itemCount[$placeholder]-$v[$j]==$itemCount[$placeholder-$w[$j]]&&$itemCount[$placeholder-$w[$j]]>=0&&$itemCount[$placeholder]-$v[$j]){//if placeholder-weight of j equals placeholder - value of j, j is part of array $knapsackHolds[]=array('w'=>$w[$j],'v'=>$v[$j]); $placeholder-=$w[$j]; break; }; }; }; echo 'KnapsackContents dump: <pre>'; var_dump($knapsackHolds); echo '</pre>'; return $knapsackHolds; }; ?>

3v4l.org

Active branches

Archived branches