3v4l.org

run code in 300+ PHP versions simultaneously
<?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; }; ?>
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 42) Position 1 = 14
Branch analysis from position: 14
2 jumps found. (Code = 44) Position 1 = 17, Position 2 = 11
Branch analysis from position: 17
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 11
2 jumps found. (Code = 44) Position 1 = 17, Position 2 = 11
Branch analysis from position: 17
Branch analysis from position: 11
filename:       /in/kF43n
function name:  (null)
number of ops:  44
compiled vars:  !0 = $w, !1 = $v, !2 = $C, !3 = $itemCount, !4 = $i, !5 = $knapsackResult, !6 = $knapsackContentsResult
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
    5     0  E >   ASSIGN                                                   !0, <array>
    6     1        INIT_FCALL                                               'array_map'
          2        SEND_VAL                                                 'round'
          3        SEND_VAR                                                 !0
          4        DO_ICALL                                         $8      
          5        ASSIGN                                                   !0, $8
    7     6        ASSIGN                                                   !1, <array>
    8     7        ASSIGN                                                   !2, 10
    9     8        ASSIGN                                                   !3, <array>
   10     9        ASSIGN                                                   !4, 0
         10      > JMP                                                      ->14
   11    11    >   ASSIGN_DIM                                               !3, !4
         12        OP_DATA                                                  0
   10    13        PRE_INC                                                  !4
         14    >   COUNT                                            ~16     !2
         15        IS_SMALLER                                               !4, ~16
         16      > JMPNZ                                                    ~17, ->11
   14    17    >   INIT_FCALL_BY_NAME                                       'Knapsack'
         18        SEND_VAR_EX                                              !1
         19        SEND_VAR_EX                                              !0
         20        SEND_VAR_EX                                              !2
         21        DO_FCALL                                      0  $18     
         22        ASSIGN                                                   !5, $18
   15    23        CONCAT                                           ~20     'Knapsack+is%3A+', !5
         24        ECHO                                                     ~20
   16    25        ECHO                                                     '%3Cpre%3E'
   17    26        INIT_FCALL                                               'var_dump'
         27        SEND_VAR                                                 !3
         28        DO_ICALL                                                 
   18    29        ECHO                                                     '%3C%2Fpre%3E'
   20    30        ECHO                                                     'elements+are%3A+%3Cpre%3E'
   21    31        INIT_FCALL_BY_NAME                                       'KnapsackContents'
         32        SEND_VAR_EX                                              !5
         33        SEND_VAR_EX                                              !3
         34        SEND_VAR_EX                                              !0
         35        SEND_VAR_EX                                              !1
         36        SEND_VAR_EX                                              !2
         37        DO_FCALL                                      0  $22     
         38        ASSIGN                                                   !6, $22
   22    39        INIT_FCALL                                               'var_dump'
         40        SEND_VAR                                                 !6
         41        DO_ICALL                                                 
   23    42        ECHO                                                     '%3C%2Fpre%3E'
   99    43      > RETURN                                                   1

Function knapsack:
Finding entry points
Branch analysis from position: 0
2 jumps found. (Code = 43) Position 1 = 10, Position 2 = 11
Branch analysis from position: 10
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 11
1 jumps found. (Code = 42) Position 1 = 29
Branch analysis from position: 29
2 jumps found. (Code = 44) Position 1 = 31, Position 2 = 13
Branch analysis from position: 31
1 jumps found. (Code = 42) Position 1 = 45
Branch analysis from position: 45
2 jumps found. (Code = 44) Position 1 = 47, Position 2 = 33
Branch analysis from position: 47
1 jumps found. (Code = 42) Position 1 = 57
Branch analysis from position: 57
2 jumps found. (Code = 44) Position 1 = 59, Position 2 = 51
Branch analysis from position: 59
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 51
2 jumps found. (Code = 43) Position 1 = 54, Position 2 = 56
Branch analysis from position: 54
2 jumps found. (Code = 44) Position 1 = 59, Position 2 = 51
Branch analysis from position: 59
Branch analysis from position: 51
Branch analysis from position: 56
Branch analysis from position: 33
2 jumps found. (Code = 43) Position 1 = 36, Position 2 = 42
Branch analysis from position: 36
1 jumps found. (Code = 42) Position 1 = 44
Branch analysis from position: 44
2 jumps found. (Code = 44) Position 1 = 47, Position 2 = 33
Branch analysis from position: 47
Branch analysis from position: 33
Branch analysis from position: 42
2 jumps found. (Code = 44) Position 1 = 47, Position 2 = 33
Branch analysis from position: 47
Branch analysis from position: 33
Branch analysis from position: 13
2 jumps found. (Code = 43) Position 1 = 16, Position 2 = 26
Branch analysis from position: 16
1 jumps found. (Code = 42) Position 1 = 28
Branch analysis from position: 28
2 jumps found. (Code = 44) Position 1 = 31, Position 2 = 13
Branch analysis from position: 31
Branch analysis from position: 13
Branch analysis from position: 26
2 jumps found. (Code = 44) Position 1 = 31, Position 2 = 13
Branch analysis from position: 31
Branch analysis from position: 13
filename:       /in/kF43n
function name:  Knapsack
number of ops:  65
compiled vars:  !0 = $v, !1 = $w, !2 = $C, !3 = $sol, !4 = $mySol, !5 = $myFinalSol, !6 = $N, !7 = $i
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   27     0  E >   RECV                                             !0      
          1        RECV                                             !1      
          2        RECV                                             !2      
   28     3        ASSIGN                                                   !3, <array>
   29     4        ASSIGN                                                   !4, <array>
   30     5        ASSIGN                                                   !5, <array>
   31     6        COUNT                                            ~11     !0
          7        ASSIGN                                                   !6, ~11
   35     8        IS_EQUAL                                                 !2, 0
          9      > JMPZ                                                     ~13, ->11
   36    10    > > RETURN                                                   0
   44    11    >   ASSIGN                                                   !7, 0
         12      > JMP                                                      ->29
   45    13    >   FETCH_DIM_R                                      ~15     !1, !7
         14        IS_SMALLER_OR_EQUAL                                      ~15, !2
         15      > JMPZ                                                     ~16, ->26
   46    16    >   INIT_FCALL_BY_NAME                                       'Knapsack'
         17        SEND_VAR_EX                                              !0
         18        SEND_VAR_EX                                              !1
         19        FETCH_DIM_R                                      ~18     !1, !7
         20        SUB                                              ~19     !2, ~18
         21        SEND_VAL_EX                                              ~19
         22        DO_FCALL                                      0  $20     
         23        ASSIGN_DIM                                               !3, !7
         24        OP_DATA                                                  $20
         25      > JMP                                                      ->28
   48    26    >   ASSIGN_DIM                                               !3, !7
         27        OP_DATA                                                  0
   44    28    >   PRE_INC                                                  !7
         29    >   IS_SMALLER                                               !7, !6
         30      > JMPNZ                                                    ~23, ->13
   54    31    >   ASSIGN                                                   !7, 0
         32      > JMP                                                      ->45
   55    33    >   FETCH_DIM_R                                      ~25     !1, !7
         34        IS_SMALLER_OR_EQUAL                                      ~25, !2
         35      > JMPZ                                                     ~26, ->42
   56    36    >   FETCH_DIM_R                                      ~28     !3, !7
         37        FETCH_DIM_R                                      ~29     !0, !7
         38        ADD                                              ~30     ~28, ~29
         39        ASSIGN_DIM                                               !4, !7
         40        OP_DATA                                                  ~30
         41      > JMP                                                      ->44
   59    42    >   ASSIGN_DIM                                               !4, !7
         43        OP_DATA                                                  0
   54    44    >   PRE_INC                                                  !7
         45    >   IS_SMALLER                                               !7, !6
         46      > JMPNZ                                                    ~33, ->33
   65    47    >   FETCH_DIM_R                                      ~34     !4, 1
         48        ASSIGN                                                   !5, ~34
   66    49        ASSIGN                                                   !7, 0
         50      > JMP                                                      ->57
   67    51    >   FETCH_DIM_R                                      ~37     !4, !7
         52        IS_SMALLER                                               !5, ~37
         53      > JMPZ                                                     ~38, ->56
   68    54    >   FETCH_DIM_R                                      ~39     !4, !7
         55        ASSIGN                                                   !5, ~39
   66    56    >   PRE_INC                                                  !7
         57    >   IS_SMALLER                                               !7, !6
         58      > JMPNZ                                                    ~42, ->51
   71    59    >   FETCH_W                      global              $43     'GLOBALS'
         60        FETCH_DIM_W                                      $44     $43, 'itemCount'
         61        ASSIGN_DIM                                               $44, !2
         62        OP_DATA                                                  !5
   72    63      > RETURN                                                   !5
   73    64*     > RETURN                                                   null

End of function knapsack

Function knapsackcontents:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 42) Position 1 = 57
Branch analysis from position: 57
2 jumps found. (Code = 44) Position 1 = 59, Position 2 = 23
Branch analysis from position: 59
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 23
1 jumps found. (Code = 42) Position 1 = 54
Branch analysis from position: 54
2 jumps found. (Code = 44) Position 1 = 57, Position 2 = 25
Branch analysis from position: 57
Branch analysis from position: 25
2 jumps found. (Code = 46) Position 1 = 33, Position 2 = 38
Branch analysis from position: 33
2 jumps found. (Code = 46) Position 1 = 39, Position 2 = 43
Branch analysis from position: 39
2 jumps found. (Code = 43) Position 1 = 44, Position 2 = 53
Branch analysis from position: 44
1 jumps found. (Code = 42) Position 1 = 57
Branch analysis from position: 57
Branch analysis from position: 53
2 jumps found. (Code = 44) Position 1 = 57, Position 2 = 25
Branch analysis from position: 57
Branch analysis from position: 25
Branch analysis from position: 43
Branch analysis from position: 38
filename:       /in/kF43n
function name:  KnapsackContents
number of ops:  66
compiled vars:  !0 = $total, !1 = $itemCount, !2 = $w, !3 = $v, !4 = $C, !5 = $knapsackHolds, !6 = $knapsackHoldsValue, !7 = $placeholder, !8 = $j
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   75     0  E >   RECV                                             !0      
          1        RECV                                             !1      
          2        RECV                                             !2      
          3        RECV                                             !3      
          4        RECV                                             !4      
   78     5        ASSIGN                                                   !5, <array>
   79     6        ASSIGN                                                   !6, <array>
   80     7        INIT_FCALL                                               'end'
          8        SEND_REF                                                 !1
          9        DO_ICALL                                                 
   81    10        INIT_FCALL                                               'key'
         11        SEND_VAR                                                 !1
         12        DO_ICALL                                         $12     
         13        ASSIGN                                                   !7, $12
   83    14        INIT_FCALL                                               'array_reverse'
         15        SEND_VAR                                                 !3
         16        DO_ICALL                                         $14     
         17        ASSIGN                                                   !3, $14
   84    18        INIT_FCALL                                               'array_reverse'
         19        SEND_VAR                                                 !2
         20        DO_ICALL                                         $16     
         21        ASSIGN                                                   !2, $16
   85    22      > JMP                                                      ->57
   86    23    >   ASSIGN                                                   !8, 0
         24      > JMP                                                      ->54
   87    25    >   FETCH_DIM_R                                      ~19     !1, !7
         26        FETCH_DIM_R                                      ~20     !3, !8
         27        SUB                                              ~21     ~19, ~20
         28        FETCH_DIM_R                                      ~22     !2, !8
         29        SUB                                              ~23     !7, ~22
         30        FETCH_DIM_R                                      ~24     !1, ~23
         31        IS_EQUAL                                         ~25     ~21, ~24
         32      > JMPZ_EX                                          ~25     ~25, ->38
         33    >   FETCH_DIM_R                                      ~26     !2, !8
         34        SUB                                              ~27     !7, ~26
         35        FETCH_DIM_R                                      ~28     !1, ~27
         36        IS_SMALLER_OR_EQUAL                              ~29     0, ~28
         37        BOOL                                             ~25     ~29
         38    > > JMPZ_EX                                          ~25     ~25, ->43
         39    >   FETCH_DIM_R                                      ~30     !1, !7
         40        FETCH_DIM_R                                      ~31     !3, !8
         41        SUB                                              ~32     ~30, ~31
         42        BOOL                                             ~25     ~32
         43    > > JMPZ                                                     ~25, ->53
   88    44    >   FETCH_DIM_R                                      ~34     !2, !8
         45        INIT_ARRAY                                       ~35     ~34, 'w'
         46        FETCH_DIM_R                                      ~36     !3, !8
         47        ADD_ARRAY_ELEMENT                                ~35     ~36, 'v'
         48        ASSIGN_DIM                                               !5
         49        OP_DATA                                                  ~35
   89    50        FETCH_DIM_R                                      ~37     !2, !8
         51        ASSIGN_OP                                     2          !7, ~37
   90    52      > JMP                                                      ->57
   86    53    >   PRE_INC                                                  !8
         54    >   COUNT                                            ~40     !3
         55        IS_SMALLER                                               !8, ~40
         56      > JMPNZ                                                    ~41, ->25
   85    57    >   IS_SMALLER                                               0, !7
         58      > JMPNZ                                                    ~42, ->23
   94    59    >   ECHO                                                     'KnapsackContents+dump%3A+%3Cpre%3E'
   95    60        INIT_FCALL                                               'var_dump'
         61        SEND_VAR                                                 !5
         62        DO_ICALL                                                 
   96    63        ECHO                                                     '%3C%2Fpre%3E'
   97    64      > RETURN                                                   !5
   98    65*     > RETURN                                                   null

End of function knapsackcontents

Generated using Vulcan Logic Dumper, using php 8.0.0


preferences:
157.17 ms | 1412 KiB | 23 Q