Subset-Sum-Problem/subset.php at master · burento/Subset-Sum-Problem · GitHub

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
<!DOCTYPE html>
<html>
<head>
	<title>Subset Sum Problem</title>
	<meta charset="utf-8">
</head>
<body>
	<?php
	   $mtime = microtime();
	   $mtime = explode(" ",$mtime);
	   $mtime = $mtime[1] + $mtime[0];
	   $starttime = $mtime;
	?>
	<?php
		set_time_limit(120);

		$gcount = 0;

		$set = array(18897109, 12828837, 9461105, 6371773, 5965343, 5946800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279833, 3095313, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, 2134411);

		$needle = 100000000;
		$sum = 0;


		//$set = array(1, 9, 5, 3, 8);
		//$needle = 13;

		foreach ($set as $k => $v){
			$sum += $v;
		}

		function evaluate_array($s, $sum){
			$arr = array();
			$arr[0] = 0;

			//Psuedo code provided by http://www.cs.utsa.edu/~wagner/CS3343/ss/ss.html
			foreach ($s as $k => $v) {
				echo "testing: " . $v . "<br/>";
				for( $i = 0; $i <= $sum; $i++){
					if( isset($arr[$i]) ){
						if( $arr[$i] != $v && $i + $v < $sum){
							if( !isset($arr[$i + $v]) ){
								$arr[$i + $v] = $v;
							}
						}
					}
				}
			}

			return $arr;
		}

		function solve($set, $sum, $needle){
			$stack = evaluate_array($set, $sum);

			echo "Size: " . sizeof($stack) . "<br/><br/>";
			while ($needle > 0){
				echo $stack[$needle] . "<br/>";
				$needle -= $stack[$needle];
			}
		}

		function brute_force($set, $needle){
			global $gcount;
			$gcount++;
			$sub = array(
				'found' => false
				, 'vals' => array()
				);

			$workset = $set;

			foreach($workset as $k => $v){
				if( $v == $needle){
					$sub['found'] = true;
					array_push($sub['vals'], $v);
					return $sub;
				}else{
					array_shift($workset);
					if( $needle - $v < 0){ return $sub; }
					$r = brute_force($workset, $needle - $v);
					if( $r['found'] ){
						array_push($r['vals'], $v);
						return $r;
					}
				}
			}

			return $sub;

		}

		function solve_bf($set, $needle){
			global $gcount;
			$sub = brute_force($set, $needle);
			$sum = 0;
			foreach($sub['vals'] as $k => $v){
				echo $v . "<br/>";
				$sum += $v;
			}

			echo "<br/>Sum: " . $sum;
			echo "<br/># Recursions: " . $gcount;
		}

		//solve($set, $sum, $needle);
		solve_bf($set, $needle);


	?>
	<?php
	   $mtime = microtime();
	   $mtime = explode(" ",$mtime);
	   $mtime = $mtime[1] + $mtime[0];
	   $endtime = $mtime;
	   $totaltime = ($endtime - $starttime);
	   echo "<br/><br/>This page was created in ".$totaltime." seconds.";
	?>
</body>
</html>