Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php
- //Unbounded knapsack problem
- //still need to figure out how many of each size
- //<?php
- $w=array(1,2,3,4);
- $v=array(1,2.2,3.3,4.4);
- $itemCount=array();
- for($i=0;$i<count($v);$i++){
- $itemCount[]=0;
- };
- $C=16;//max weight limit of knapsack
- echo 'Knapsack is: '.Knapsack($v,$w,$C,$itemCount);
- //(N = # different items)
- function Knapsack($v,$w,$C,$itemCount){
- $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++){
- echo 'ORIGINAL Knapsack I: '.$i.
- if($C>=$w[$i]){
- $GLOBALS["itemCount"][$i]+=1;
- echo ' GLOBALS itemCount['.$i.']='.$GLOBALS["itemCount"][$i].' i='.$i."\n";
- //echo 'capacity('.$C.')>w[i]('.$w[$i].')<br />';
- $sol[$i] = Knapsack($v,$w,$C-$w[$i],$GLOBALS["itemCount"]);// Knapsack capacity reduced by w[i]
- echo ' for loop 1 '."\n".'i: '.$i.' $sol[$i]: '.$sol[$i]."\n\n";
- } // because it has item i packed in
- // it already
- else{$sol[$i] = 0;} // Not enough space to pack item i
- }
- //var_dump($sol);
- /* ---------------------------------------------
- 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]
- echo ' for loop 2 '."\n".'i: '.$i.' $mySol[$i]: '.$mySol[$i]."\n\n<br />";
- echo '<strong> TO ADD V[i]'.$v[$i].'</strong><br />';
- } // 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=1;$i<$N;$i++){
- if($mySol[$i]>$myFinalSol){
- $myFinalSol = $mySol[$i];}
- }
- return $myFinalSol;
- };
- //?>
- ?>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement