This is a basic PHP program which describes Dynamic Programming solution for subset sum problem. Below examples will help you in the better understanding of the basic concept of PHP programming language.
You need to have a basic knowledge of for loop in PHP programming language. Copy the below code and execute it with the help of PHP compiler.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | <?php /* * A Dynamic Programming solution for subset sum problem */ function isSubsetSum( $set, $n, $sum) { $subset = array(array()); // If sum is 0, then answer is true for ( $i = 0; $i <= $n; $i++) $subset[$i][0] = true; for ( $i = 1; $i <= $sum; $i++) $subset[0][$i] = false; for ($i = 1; $i <= $n; $i++) { for ($j = 1; $j <= $sum; $j++) { if($j < $set[$i-1]) $subset[$i][$j] = $subset[$i-1][$j]; if ($j >= $set[$i-1]) $subset[$i][$j] = $subset[$i-1][$j] || $subset[$i - 1][$j - $set[$i-1]]; } } for (int i = 0; i <= n; i++) { for (int j = 0; j <= sum; j++) printf ("%4d", subset[i][j]); printf("n"); }*/ return $subset[$n][$sum]; } $set = array(3, 34, 4, 12, 5, 2); $sum = 9; $n = count($set); if (isSubsetSum($set, $n, $sum) == true) echo "Found a subset with given sum"; else echo "No subset with given sum"; ?> |
Found a subset with given sum
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
