<code>有一个数组,由30个1~999键值组成,和为 12865,请写出计算此数组的 30 个值的方法 $arr[1]+$arr[2]+....+$arr[30]=12865</code>
如何把以下代码简化,因为 $i ~ $iN 是不确定的。如果有其他算法更好
<code> function loopDeep($sum , $count, $min, $max) { for ($i = $min; $i </code>
2015-8-23 一种算法,查看分布。(by CSDN某大牛)
$r = foo(12865, 30); echo array_sum($r), PHP_EOL; //验证总和 print_r(array_count_values($r)); //查看分布 function foo($num, $k, $min = 1, $max = 999) { $res = array_fill(0, $k, 1); do { for ($i = 0; $i < $k; $i++) { $sum = array_sum($res); $t = rand(0, $max - $min); if ($res[$i] + $t > $max) $t = $max - $res[$i]; if ($sum + $t > $num) $t = $num - $sum; $res[$i] += $t; } } while ($num > $sum); return $res; }
12865 Array ( [222] => 2 [589] => 1 [127] => 1 [538] => 1 [268] => 1 [444] => 1 [922] => 1 [537] => 1 [211] => 1 [17] => 1 [848] => 1 [800] => 1 [893] => 1 [274] => 1 [499] => 1 [45] => 1 [660] => 1 [686] => 1 [968] => 1 [491] => 1 [355] => 1 [849] => 1 [857] => 1 [322] => 1 [217] => 1 [1] => 4 )
<code>有一个数组,由30个1~999键值组成,和为 12865,请写出计算此数组的 30 个值的方法 $arr[1]+$arr[2]+....+$arr[30]=12865</code>
如何把以下代码简化,因为 $i ~ $iN 是不确定的。如果有其他算法更好
<code> function loopDeep($sum , $count, $min, $max) { for ($i = $min; $i < $max; $i++) { for ($i2 = $min; $i2 < $max; $i2++) { for ($i3 = $min; $i3 < $max; $i3++) { for ($i4 = $min; $i4 < $max; $i4++) { if ($i + $i2 + $i3 + $i4 == $sum) { return [$i, $i2, $i3]; } } } } } return []; } </code>
2015-8-23 一种算法,查看分布。(by CSDN某大牛)
$r = foo(12865, 30); echo array_sum($r), PHP_EOL; //验证总和 print_r(array_count_values($r)); //查看分布 function foo($num, $k, $min = 1, $max = 999) { $res = array_fill(0, $k, 1); do { for ($i = 0; $i < $k; $i++) { $sum = array_sum($res); $t = rand(0, $max - $min); if ($res[$i] + $t > $max) $t = $max - $res[$i]; if ($sum + $t > $num) $t = $num - $sum; $res[$i] += $t; } } while ($num > $sum); return $res; }
12865 Array ( [222] => 2 [589] => 1 [127] => 1 [538] => 1 [268] => 1 [444] => 1 [922] => 1 [537] => 1 [211] => 1 [17] => 1 [848] => 1 [800] => 1 [893] => 1 [274] => 1 [499] => 1 [45] => 1 [660] => 1 [686] => 1 [968] => 1 [491] => 1 [355] => 1 [849] => 1 [857] => 1 [322] => 1 [217] => 1 [1] => 4 )
正准备睡觉,瞬间有了思路。。。
先来个js版本的---我是前端(:
<code>function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){ if($loop_index==$loop_num){ if($sum==$sum_end){ console.log('///$sum:'+$sum+'/$sum_end:'+$sum_end+'/$indexArr:'+$indexArr+'/$loop_index:'+$loop_index); } return false; }else{ for(var $ii=$i;$ii<=$max;$ii++){ $indexArr[$loop_index]=$ii; if($indexArr[$loop_index]>($max-$loop_num+1+$loop_index)){ break; } $sum=eval($indexArr.join("+")); console.log('$sum:'+$sum+'/$sum_end:'+$sum_end+'/$loop_index:'+$loop_index+'/$ii:'+$ii+'/$indexArr:'+$indexArr); forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr); } } }; function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){ for(var $i=$min;$i<=$max-$loop_num+1;$i++){ var $loop_index=0; $indexArr[$loop_index]=$i; forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr) } } addFn(0,999,0,12865,30,0,[])</code>
php:
<code> function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){ if($loop_index==$loop_num){ if($sum==$sum_end){ echo('///$sum:'.$sum.'/$sum_end:'.$sum_end.'/$indexArr:'.$indexArr); print_r($indexArr); }; return false; }else{ for($ii=$i;$ii<$max;$ii++){ $indexArr[$loop_index]=$ii; if($indexArr[$loop_index]>($max-$loop_num+1+$loop_index)){ break; } $sum=array_sum($indexArr); forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr); } } }; function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){ for($i=$min;$i<($max-$loop_num+1);$i++){ $loop_index=0; $indexArr[$loop_index]=$i; forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr) } } addFn(0,999,0,12865,30,0,[])</code>
刚刚用node跑了一下,没跑完(复杂度太大),也不知道对不对,谁跑完结果告诉我一下(:
可以睡觉去了。。。
用测试数据0,1,2,3跑了一下
[0,1,2,3]取3个数字,和为6;
<code>addFn(0,3,0,6,3,0,[])</code>
dp, 只用一维数组节省内存, 但是题目复杂度太大... 不玩了.
<code>public Set<List<Integer>> compute(int N, int SUM, int MAX_KEY) { Set<List<Integer>>[] pre = null; Set<List<Integer>>[] cur = new Set[SUM + 1]; // one elem for (int i = 0; i <= MAX_KEY; i++) { cur[i] = new HashSet<>(); cur[i].add(Collections.singletonList(i)); } for (int i = 2; i <= N; i++) { pre = cur; cur = new Set[SUM + 1]; for (int j = 0; j <= SUM; j++) for (int k = 0; k <= MAX_KEY; k++) if (j - k >= 0 && pre[j - k] != null) { if (cur[j] == null) cur[j] = new HashSet<>(); for (List<Integer> l: pre[j - k]) { List<Integer> tmp = new ArrayList<>(l); tmp.add(k); Collections.sort(tmp); cur[j].add(tmp); } } } return cur[SUM]; } @Test public void test(){ compute(30, 12865, 999); } </code>
二维数组, 太费内存
<code>private Set<List<Integer>>[][] dp = null; private Set<List<Integer>> res = null; public Set<List<Integer>> compute(int N, int SUM, int MAX_KEY) { dp = new Set[N + 1][SUM + 1]; for (int i = 0; i <= MAX_KEY; i++) { dp[1][i] = new HashSet<>(); dp[1][i].add(Collections.singletonList(i)); } for (int i = 2; i <= N; i++) for (int j = 0; j <= SUM; j++) for (int k = 0; k <= MAX_KEY; k++) if (j - k >= 0 && dp[i - 1][j - k] != null) { if (dp[i][j] == null) dp[i][j] = new HashSet<>(); for (List<Integer> l: dp[i - 1][j - k]) { List<Integer> tmp = new ArrayList<>(l); tmp.add(k); dp[i][j].add(tmp); } } return dp[N][SUM]; } </code>
Java代码. 用了一些优化提高效率, 但复杂度还是太高. 权当参考吧.
<code>private Set<Long> failedSet = null; private Set<List<Integer>> res = null; public Set<List<Integer>> compute() { failedSet = new HashSet<>(); res = new HashSet<>(); computeInt(30, 12865, 999, new int[30]); return res; } private boolean computeInt(int count, int sum, int max, int[] arr) { if (count == 0 || sum < 0) { if (sum == 0){ List<Integer> tmp = Arrays.stream(arr).sorted().boxed() .collect(Collectors.toList()); res.add(tmp); } return sum == 0; } long key = (long)count * Integer.MAX_VALUE + sum; if (failedSet.contains(key)) return false; boolean found = false; for (int i = 0; i <= max; i++) { arr[count - 1] = i; if (computeInt(count - 1, sum - i, Math.min(max, i), arr)) found = true; } if (!found) failedSet.add(key); return found; }</code>
题目意思比较含糊,没说要所有结果还是只要一组还是搜索特定结果;
只要一组,数字可以重复的话,29个1加一个12836就可以了;
只要一组数字,数字要求不重复,随机生成29个,sum超过12865和重复数字的回退,最后一个用12865减掉前面29个值;
如果搜索给定的数组的话,直接DFS吧;
如果是求出所有可能结果,那就BFS吧。