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