欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

PHP回溯法解決0-1背包問題實(shí)例分析

 更新時間:2015年03月23日 11:03:34   作者:瘋狂一夏  
這篇文章主要介紹了PHP回溯法解決0-1背包問題,實(shí)例分析了php回溯法解決背包問題的技巧,具有一定參考借鑒價值,需要的朋友可以參考下

本文實(shí)例講述了PHP回溯法解決0-1背包問題的方法。分享給大家供大家參考。具體分析如下:

這段代碼是根據(jù)《軟件設(shè)計師》教程的偽代碼寫的;
最麻煩的不是偽代碼改成php,而是數(shù)組下標(biāo)從0開始,及相應(yīng)的下標(biāo)判斷問題;
帶著調(diào)試輸出一塊寫上

<?php
  $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<$n;$i++){
      $c = $c + $w_arr[$i];
      //var_dump($W_total);var_dump($c);
      if($c<$W_total)
        $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<$n && $cw+$w_arr[$k]<=$W_total){
        $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)<=$fp)
      {
        while($k>=0 && $Y_arr[$k]!=1){
          $k -= 1;
        }
        if($k<0)
        {
          return $X_arr;
        }
        var_dump($k);
        $Y_arr[$k] = 0;
        $cw -= $w_arr[$k];
        $cp -= $v_arr[$k];
      }
      $k += 1;
    }
  }
?>

希望本文所述對大家的php程序設(shè)計有所幫助。

相關(guān)文章

  • php 文件狀態(tài)緩存帶來的問題

    php 文件狀態(tài)緩存帶來的問題

    當(dāng)使用以下函數(shù)時,會因?yàn)槲募顟B(tài)緩存,導(dǎo)致結(jié)果錯誤
    2008-12-12
  • PHP基于簡單遞歸函數(shù)求一個數(shù)階乘的方法示例

    PHP基于簡單遞歸函數(shù)求一個數(shù)階乘的方法示例

    這篇文章主要介紹了PHP基于簡單遞歸函數(shù)求一個數(shù)階乘的方法,結(jié)合實(shí)例形式分析了php遞歸函數(shù)的定義與數(shù)學(xué)運(yùn)算簡單操作技巧,需要的朋友可以參考下
    2017-04-04
  • PHP常用設(shè)計模式之委托設(shè)計模式

    PHP常用設(shè)計模式之委托設(shè)計模式

    委托是對一個類的功能進(jìn)行擴(kuò)展和復(fù)用的方法。它的做法是:寫一個附加的類提供附加的功能,并使用原來的類的實(shí)例提供原有的功能,接下來通過本文給大家介紹PHP委托設(shè)計模式實(shí)例詳解,感興趣的朋友一起學(xué)習(xí)吧
    2016-02-02
  • php+mysql實(shí)現(xiàn)的無限分類方法類定義與使用示例

    php+mysql實(shí)現(xiàn)的無限分類方法類定義與使用示例

    這篇文章主要介紹了php+mysql實(shí)現(xiàn)的無限分類方法類定義與使用,結(jié)合實(shí)例形式分析了php+mysql無限分類方法類基本定義與使用方法,需要的朋友可以參考下
    2020-05-05
  • PHP的幾個常用加密函數(shù)

    PHP的幾個常用加密函數(shù)

    在網(wǎng)站的開發(fā)過程中,常常需要對部分?jǐn)?shù)據(jù)(如用戶密碼)進(jìn)行加密,本文主要介紹PHP的幾個常見的加密函數(shù),需要的朋友可以參考下
    2016-02-02
  • PHP實(shí)現(xiàn)變色驗(yàn)證碼實(shí)例

    PHP實(shí)現(xiàn)變色驗(yàn)證碼實(shí)例

    驗(yàn)證碼想必大家都有見到過吧,在本文為大家介紹下PHP如何實(shí)現(xiàn)變色驗(yàn)證碼,感興趣的朋友可以參考下
    2014-01-01
  • 利用PHP實(shí)現(xiàn)開心消消樂的算法示例

    利用PHP實(shí)現(xiàn)開心消消樂的算法示例

    開心消消樂應(yīng)該對大家來說都不陌生吧,下面這篇文章主要給大家介紹了關(guān)于如何利用PHP實(shí)現(xiàn)開心消消樂算法的相關(guān)資料,文中將需求和示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2017-10-10
  • 使用Codeigniter重寫insert的方法(推薦)

    使用Codeigniter重寫insert的方法(推薦)

    下面小編就為大家?guī)硪黄褂肅odeigniter重寫insert的方法(推薦)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-03-03
  • thinkphp5.0自定義驗(yàn)證規(guī)則使用方法

    thinkphp5.0自定義驗(yàn)證規(guī)則使用方法

    本文主要講了thinkphp5.0版本中自定義驗(yàn)證規(guī)則的使用方法和一些注意事項(xiàng)。
    2017-11-11
  • 關(guān)于URL最大長度限制的相關(guān)資料查證

    關(guān)于URL最大長度限制的相關(guān)資料查證

    這篇文章主要介紹了關(guān)于URL最大長度限制的相關(guān)資料查證,這里記錄一下,方便以后使用。
    2014-12-12

最新評論