PHP回溯法解决0-1背包问题实例分析
这篇文章主要介绍了PHP回溯法解决0-1背包问题,实例分析了php回溯法解决背包问题的技巧,具有一定参考借鉴价值,需要的朋友可以参考下
本文实例讲述了PHP回溯法解决0-1背包问题的方法。分享给大家供大家参考。具体分析如下:
这段代码是根据《软件设计师》教程的伪代码写的;
最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题;
带着调试输出一块写上
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
$v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bknap1(110)); //var_dump(bound(139,89,7,110)); function bound($v,$w,$k,$W_total){ global $v_arr,$w_arr,$n; $b = $v; $c = $w; //var_dump($W_total);var_dump($n);var_dump($k);var_dump($v);var_dump($w); //die; for($i=$k+1;$i $c = $c + $w_arr[$i]; //var_dump($W_total);var_dump($c); if($c $b += $v_arr[$i]; else{ //var_dump((1-($c-$W_total)/$w_arr[$i])*$v_arr[$i]); $b = $b+(1-($c-$W_total)/$w_arr[$i])*$v_arr[$i]; return $b; } } /*var_dump('------bound head'); var_dump($k); var_dump($b); var_dump('------bound end');*/ return $b; } function bknap1($W_total){ global $v_arr,$w_arr,$n; $cw = $cp = 0; $k = 0; $fp = -1; while(true){ while($k $cw += $w_arr[$k]; $cp += $v_arr[$k]; $Y_arr[$k] = 1; $k +=1; } //var_dump($cw);var_dump($cp);var_dump($Y_arr);var_dump($k);var_dump($n); if($k==$n){ $fp = $cp; $fw = $cw; $k = $n-1; $X_arr = $Y_arr; //bound($cp,$cw,$k,$W_total); //var_dump(bound($cp,$cw,$k,$W_total),$fp,$k);die; //var_dump($fp);var_dump($fw);var_dump($Y_arr);var_dump($k);var_dump($n); }else{ $Y_arr[$k] = 0; } //var_dump($Y_arr);var_dump($k);var_dump($n);//die; //var_dump(bound($cp,$cw,$k,$W_total),$fp);die; while(bound($cp,$cw,$k,$W_total) { while($k>=0 && $Y_arr[$k]!=1){ $k -= 1; } if($k { return $X_arr; } var_dump($k); $Y_arr[$k] = 0; $cw -= $w_arr[$k]; $cp -= $v_arr[$k]; } $k += 1; } } ?> |
希望本文所述对大家的php程序设计有所帮助。

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\ \;||\xc2\xa0)/","其他字符",$str)”语句。

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

查找方法:1、用strpos(),语法“strpos("字符串值","查找子串")+1”;2、用stripos(),语法“strpos("字符串值","查找子串")+1”。因为字符串是从0开始计数的,因此两个函数获取的位置需要进行加1处理。


Outils d'IA chauds

Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool
Images de déshabillage gratuites

Clothoff.io
Dissolvant de vêtements AI

AI Hentai Generator
Générez AI Hentai gratuitement.

Article chaud

Outils chauds

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

Listes Sec
SecLists est le compagnon ultime du testeur de sécurité. Il s'agit d'une collection de différents types de listes fréquemment utilisées lors des évaluations de sécurité, le tout en un seul endroit. SecLists contribue à rendre les tests de sécurité plus efficaces et productifs en fournissant facilement toutes les listes dont un testeur de sécurité pourrait avoir besoin. Les types de listes incluent les noms d'utilisateur, les mots de passe, les URL, les charges utiles floues, les modèles de données sensibles, les shells Web, etc. Le testeur peut simplement extraire ce référentiel sur une nouvelle machine de test et il aura accès à tous les types de listes dont il a besoin.

ZendStudio 13.5.1 Mac
Puissant environnement de développement intégré PHP

Version crackée d'EditPlus en chinois
Petite taille, coloration syntaxique, ne prend pas en charge la fonction d'invite de code
