Exemple de partage d'algorithme de backtracking en php

黄舟
Libérer: 2023-03-15 19:26:01
original
1218 Les gens l'ont consulté

Une grosse vache chamelle a 2 sacs de riz, une vache moyenne chameau a un sac de riz et deux petites vaches chameaux ont un sac de riz. Combien de grosses vaches, combien de vaches moyennes et combien de veaux sont nécessaires. pour 100 sacs de riz ?

<?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);

?>
Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal