• 售前

  • 售后

热门帖子
入门百科

php回溯算法盘算组合总和的实例代码

[复制链接]
462710480 显示全部楼层 发表于 2021-8-14 14:51:29 |阅读模式 打印 上一主题 下一主题
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
阐明

所有数字(包罗目标数)都是正整数。 解集不能包含重复的组合。
实例

输入:
  1. candidates = [10,1,2,7,6,1,5], target = 8,
复制代码
所求解集为:
  1. [
  2. [1, 7],
  3. [1, 2, 5],
  4. [2, 6],
  5. [1, 1, 6]]
复制代码
解题思路

直接参考回溯算法团灭排列/组合/子集问题。
代码
  1. class Solution {
  2.     /** * @param Integer[] $candidates * @param Integer $target * @return Integer[][] */
  3.     public $res = [];
  4.     function combinationSum2($candidates, $target) {
  5.         sort($candidates);   // 排序
  6.         $this->dfs([], $candidates, $target, 0);
  7.         return $this->res;
  8.     }
  9.     function dfs($array, $candidates, $target, $start) {
  10.         if ($target < 0) return;
  11.         if ($target === 0) {
  12.             $this->res[] = $array;
  13.             return;
  14.         }
  15.         $count = count($candidates);
  16.         for ($i = $start; $i < $count; $i++) {
  17.             if ($i !== $start && $candidates[$i] === $candidates[$i - 1]) continue;
  18.             $array[] = $candidates[$i];
  19.             $this->dfs($array, $candidates, $target - $candidates[$i], $i + 1);//数字不能重复使用,需要+1
  20.             array_pop($array);
  21.     }}
复制代码
实例扩展:
  1. <?php
  2. /*
  3. * k = 2x + y + 1/2z
  4. 取值范围
  5. * 0 <= x <= 1/2k
  6. * 0 <= y <= k
  7. * 0 <= z < = 2k
  8. * x,y,z最大值 2k
  9. */
  10. $daMi = 100;
  11. $result = array();
  12. function isOk($t,$daMi,$result)
  13. {/*{{{*/
  14. $total = 0;
  15. $hash = array();
  16. $hash[1] = 2;
  17. $hash[2] = 1;
  18. $hash[3] = 0.5;
  19. for($i=1;$i<=$t;$i++)
  20. {
  21. $total += $result[$i] * $hash[$i];
  22. }
  23. if( $total <= $daMi)
  24. {
  25. return true;
  26. }
  27. return false;
  28. }/*}}}*/
  29. function backtrack($t,$daMi,$result)
  30. {/*{{{*/
  31. //递归出口
  32. if($t > 3)
  33. {
  34. //输出最优解
  35. if($daMi == (2 * $result[1] + $result[2] + 0.5 * $result[3]))
  36. {
  37.   echo "最优解,大米:${daMi},大牛:$result[1],中牛: $result[2],小牛:$result[3]\n";
  38. }
  39. return;
  40. }
  41. for($i = 0;$i <= 2 * $daMi;$i++)
  42. {
  43. $result[$t] = $i;
  44. //剪枝
  45. if(isOk($t,$daMi,$result))
  46. {
  47.   backtrack($t+1,$daMi,$result);
  48. }
  49. $result[$t] = 0;
  50. }
  51. }/*}}}*/
  52. backtrack(1,$daMi,$result);
  53. ?>
复制代码
到此这篇关于php回溯算法盘算组合总和的实例代码的文章就先容到这了,更多相干php回溯算法盘算组合总和的方法内容请搜刮草根技能分享以前的文章或继续欣赏下面的相干文章盼望各人以后多多支持草根技能分享!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作