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

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明

所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。

实例

输入:

candidates = [10,1,2,7,6,1,5], target = 8,

所求解集为:

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]]

解题思路

直接参考回溯算法团灭排列/组合/子集问题。

代码

class Solution {
    /** * @param Integer[] $candidates * @param Integer $target * @return Integer[][] */
    public $res = [];
    function combinationSum2($candidates, $target) {
        sort($candidates);   // 排序
        $this->dfs([], $candidates, $target, 0);
        return $this->res;
    }
    function dfs($array, $candidates, $target, $start) {
        if ($target < 0) return;
        if ($target === 0) {
            $this->res[] = $array;
            return;
        }
        $count = count($candidates);
        for ($i = $start; $i < $count; $i++) {
            if ($i !== $start && $candidates[$i] === $candidates[$i - 1]) continue;
            $array[] = $candidates[$i];
            $this->dfs($array, $candidates, $target - $candidates[$i], $i + 1);//数字不能重复使用,需要+1
            array_pop($array);
    }}

实例扩展：

<?php
/*
 * k = 2x + y + 1/2z
 取值范围
 * 0 <= x <= 1/2k
 * 0 <= y <= k
 * 0 <= z < = 2k
 * x,y,z最大值 2k
 */
$daMi = 100;
$result = array();
function isOk($t,$daMi,$result)
{/*{{{*/
 $total = 0;
 $hash = array();
 $hash[1] = 2;
 $hash[2] = 1;
 $hash[3] = 0.5;
 for($i=1;$i<=$t;$i++)
 {
 $total += $result[$i] * $hash[$i];
 }
 if( $total <= $daMi)
 {
 return true;
 }
 return false;
}/*}}}*/
function backtrack($t,$daMi,$result)
{/*{{{*/
 //递归出口
 if($t > 3)
 {
 //输出最优解
 if($daMi == (2 * $result[1] + $result[2] + 0.5 * $result[3]))
 {
  echo "最优解，大米:${daMi},大牛：$result[1],中牛： $result[2]，小牛：$result[3]\n";
 }
 return;
 }
 for($i = 0;$i <= 2 * $daMi;$i++)
 {
 $result[$t] = $i;
 //剪枝
 if(isOk($t,$daMi,$result))
 {
  backtrack($t+1,$daMi,$result);
 }
 $result[$t] = 0;
 }
}/*}}}*/
backtrack(1,$daMi,$result);
?>

到此这篇关于php回溯算法计算组合总和的实例代码的文章就介绍到这了,更多相关php回溯算法计算组合总和的方法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • PHP实现的回溯算法示例

    PHP实现的回溯算法示例

    本文实例讲述了PHP实现的回溯算法.分享给大家供大家参考,具体如下: 问题: 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛? 实现代码: <?php /* * k = 2x + y + 1/2z 取值范围 * 0 <= x <= 1/2k * 0 <= y <= k * 0 <= z < = 2k * x,y,z最大值 2k */ $daMi = 100; $result = array();

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

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

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的每个数字在每个组合中只能使用一次. 说明 所有数字(包括目标数)都是正整数. 解集不能包含重复的组合. 实例 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] 解题思路 直接参考回溯算法团灭排列/

  • php计算汉明距离总和的实例讲解

    两个整数的汉明距离指的是这两个数字的二进制数对应位不同的数量. 计算一个数组中,任意两个数之间汉明距离的总和. 实例 输入: 4, 14, 2 输出: 6 解释:在二进制表示中,4表示为0100,14表示为1110,2表示为0010.(这样表示是为了体现后四位之间关系) 所以答案为:HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6. 注意: 数组中元素的范围为从 0到 1

  • Ajax实现动态加载组合框的实例代码

    一  province.jsp <%@ page language="java" import="java.util.*" pageEncoding="UTF-8"%> <html> <head> <script type="text/javascript" language="javaScript"> var xmlHttp = false; //全局变量,

  • C#根据日期计算星期几的实例代码

    本示例采用基姆拉尔森计算公式来根据日期计算未来日子是星期几: 首先看下百度百科的基姆拉尔森计算公式定义: 基姆拉尔森计算公式 W= (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400) mod 7 在公式中d表示日期中的日数,m表示月份数,y表示年数. 注意:在公式中有个与其他公式不同的地方: 把一月和二月看成是上一年的十三月和十四月,例:如果是2004-1-10则换算成:2003-13-10来代入公式计算. 1.客户端(采用ajax方式调用): $.get('Caculate

  • java根据开始时间结束时间计算中间间隔日期的实例代码

    具体代码如下所述: import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.ArrayList; import java.util.Calendar; import java.util.Date; import java.util.List; public class Test { public static List<String> findDates(String stime,

  • python自动分箱,计算woe,iv的实例代码

    笔者之前用R开发评分卡时,需要进行分箱计算woe及iv值,采用的R包是smbinning,它可以自动进行分箱.近期换用python开发, 也想实现自动分箱功能,找到了一个woe包,地址https://pypi.org/project/woe/,可以直接 pip install woe安装. 由于此woe包官网介绍及给的例子不是很好理解,关于每个函数的使用也没有很详细的说明,经过一番仔细探究后以此文记录一下该woe包的使用及其计算原理. 例子 官方给的例子不是很好理解,以下是我写的一个使用示例.以

  • iOS中的缓存计算和清除完整实例代码

    1.首先,一般我们项目中的缓存一般分为2大块,一个是自己缓存的一些数据;还有一个就是我们使用的SDWebImage这个第三方库给我们自动缓存的图片文件缓存了 <1>怎么计算缓存大小(主要是利用系统提供的NSFileManager类来实现) $1.单个文件大小的计算 -(long long)fileSizeAtPath:(NSString *)path{ NSFileManager *fileManager=[NSFileManager defaultManager]; if([fileMana

  • C++贪心算法实现活动安排问题(实例代码)

    贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择.也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解. 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关. 具体代码如下所示: #include <cstdio> #include <iostream> #include <ctime> #include <

  • java实现Composite组合模式的实例代码

    java实现Composite组合模式的实例代码

    //20210121 写在前面:刚期末考试完,考了面向对象,里边儿有23个设计模式,我寻思着考完挨个儿实现一下,本文实现组合模式 组合模式核心思想类似文件夹的概念,构件树形结构,树形有叶子结点和文件夹结点,文件夹结点可以包含叶子结点和文件夹结点 分为两种模式 - 透明型:所有节点构造全部相同,但是由于叶子结点没有下层结点,所以其有些方法为空,会不安全 - 安全型:叶子结点和文件架节点构造不同,这样展示的时候需要判断节点属性,不方便调用,但是由于没有空方法,会很安全 透明型组合模式程序源代码: /

  • OpenCV计算平均值cv::mean实例代码

    OpenCV计算平均值cv::mean实例代码

    前言 opencv中封装了一个专门用于求解cv::Mat均值的函数,即cv::mean(&cv::Mat),该函数会得到Mat中各个通道的均值,若要获取指定通道的均值,做进一步解析即可. 下面给出opencv的官方说明: Operations on Arrays 函数原型 Scalar mean(InputArray src, InputArray mask = noArray()); 参数说明 InputArray类型的src,输入图像,如Mat类型. InputArray类型的mask,掩膜

随机推荐