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

php回溯算法计算组合总和的实例代码 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的每个数字在每个组合中只能使用一次. 说明 所有数字(包括目标数)都是正整数. 解集不能包含重复的组

给定一个数组 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回溯算法计算组合总和的方法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

本站部分内容来源互联网,如果有图片或者内容侵犯您的权益请联系我们删除!

相关文档推荐

php安装grpc扩展的具体步骤 1.在php.ini文件中添加grpc扩展配置:extension=grpc.so git clone -b $(curl -L https://grpc.io/release) https://github.com/grpc/grpc cd grpc git submodule update --init make make install cd src/php/ext/grpc phpize ./co
php实现自运行的实例详解 说明 1.创建一个PHP示例文件:然后输入ignore_user_abort();. 2.通过do{$fp = fopen('test.php','a')...}while(true)...方法实现任务自动执行即可. 关于PHP代码如何自动执行,我们通常做定时任务需要做到代码自动执行,往往会借助系统来
PHP解决输出中文乱码问题讲解 解决 PHP 输出中文乱码的问题 问题描述 今天给导航狗(https://daohanggou.cn/)的 PHP 程序和数据库文件迁移了服务器, 但是迁移到新的服务器上之后 PHP 输出的中文和 PHP 输出的从 MySQL 数据库查询出来的数据中的中文都出现
MySQL并发能力强、响应速度快,是性能优异的数据库软件;PHP是功能强大的服务器端脚本语言下面,以一个简单的聊天室设计为例,介绍PHP+MySQL在网页开发中的应用。 总体设计 1. 1 构思与规划: 聊天室的基本原理,就是把每个连上同一网页的用
PHP实现如何分辨全角和半角以避免乱码,实现函数如下。原理就是截断一个字符,看看其ascII码是不是大于128,如果是,说明截断的是一个全角汉字,那么就退后一个截断。用$length控制长度 备注:循环判断字符串里面的 128 的字符个数,如果半角
怎么剔除文档中的html标签,下面编程学习网的小编为大家整理了三种方案,希望能够帮到大家: 1、直接利用php的strip_tags函数实现,代码如下: ?$a="font color=red这是一个带HTML标识的字串/font";$a=strip_tags($a);print $a;? 2、利用正则表达式配合替换函