検索

ホームページ >バックエンド開発 >PHPチュートリアル >php はボクシングの問題を解決します

php はボクシングの問題を解決します

WBOY
WBOYオリジナル
2016-07-25 08:51:001188ブラウズ


ボクシング問題と石渡り問題に対する私の解決策
http://www.oschina.net/question/117304_112681 を参照してください

主な実装アイデアは次のとおりです:
1. 大きな石は最初に梱包する必要があります (早めにロードし、後で保留する) ) 後の項目はすべて梱包する必要があるので、最初に解決してください)
2. w に近い重量のアイテムを優先して梱包します。 9,5,1 の場合は 951 のパッキングが推奨されます
4. コードを簡素化するために PHP 関数を使用し、k 値に基づいて関数を生成する手法を使用します
5. このタイプの問題の性質上、計算は量が多い場合は、パラメータテストを適切に設定してください。

出力例: (rocks が 1~9、w が 15、k が 3 の場合)
3 つの要素から構成される最大解を求めます:
Array
(
[0] => 9
[1] => 5
[2] => 1
)

2 つの要素で構成される最大解を求めます:
Array
(
[0] => 9
[1] => 6
)

1 つの要素で構成される最大解を求めます解:
Array
(
[0] => 9
)

3つの要素から構成される最大解を見つけます:
Array
(
[0] => 8
[1] => 4
[2] => 3
)

2 つの要素で構成される最大解を求めます:
Array
(
[0] => 8
[1] => 7
)

1 つの要素で構成される最大解を求めます:
Array
(
[0] => 8
)

3 つの要素で構成される最大解を見つけます:
Array
(
[0] => 7
[1] => 6
[2] => 2
)

2 つの要素で構成される最大解:
Array
(
[0] => 7
[1] => 6
)

1 つの要素で構成される最大解を求めます:
Array
(
[0] => 7
) )

最小回数: 3
発送プロセス: Array
(
[0] => Array
(
[0] => 9
[1] => 5
[2] => 1
)

[1 ] => 配列
(
[0] => 8
[1] => 4
[2] => 3
)

[2] => 配列
(
[0] => 7
[1] => 6
[2] => 2
)

)
  1. // PHP演習ボクシング問題
  2. // 著者: mx (http://my.oschina.net/meikaiyuan)
  3. // 2013/5/30
  5. // 質問:
  6. / / http://www.oschina.net/question/117304_112681
  7. /*
  8. タイトル:
  10. 以前にも同様の質問をしたことがありますが、良い答えがありません。そこでもう一度聞きたいのです。
  12. 大小の石の山があり、ボートで川の反対側まで引っ張る必要があります
  13. -- m 個の石があり、それぞれの重さはわかっています
  14. -- ボートで運ぶことしかできません一度に k 個の石を積み込みます。積載重量は w
  15. を超えることはできません -- すべての石を川を渡って運ぶことができる最小往復回数を知りたいです。
  17. ------------------------------------
  18. 例 1
  19. 9 つの石があり、その重さは1,2,3,4,5,6,7,8,9
  20. k=3
  21. w=15
  22. 結果としては、少なくとも3回は発送できることになります。
  23. ------------------------------------
  24. 例 2
  25. 9 つの石があり、それぞれの重さは 1 です。 1,1,5,6,6,7,9,9
  26. k=3
  27. w=15
  28. その結果、出荷が完了するまでに少なくとも 4 回かかります。
  29. */
  31. //コードの始まり
  33. //Stones
  34. global $rocks;
  35. //船が一度に積み込める最大個数
  36. global $k;
  37. //船の最大積載量
  38. グローバル $w;
  40. $k =3;
  41. $rocks=array(1,2,3,4,5,6,7,8,9);
  42. // $rocks=array(1,1,1, 5,6,6,7, 9,9); //このデータセットに変更して結果を試してみますか?
  43. $w=15;
  45. // 現在何回出荷されていますか?
  46. $count=0;
  47. // 輸送プロセス、1=>array(9,5, の形の 2 次元配列) 1) 出荷された回数を示します 運が良かったでしょうか?
  48. $process=array();
  50. // 配列 $rocks 内で最大 $k 個の要素と次の合計が存在する組み合わせを見つけます。これらの要素は可能な限り大きく、指定された値 $w 以下です。配列は大きいものから小さいものに並べ替えられています
  51. function getMaxCombination( ) {
  52. //Stones
  53. global $rocks;
  54. //いくつ船は最大で何個まで運ぶことができますか? global $k;
  55. //船の最大積載量
  56. global $w;
  58. // すべての要素の合計が以下である最大のセットを保存しますw の中で最も大きい値です
  59. $k_w_result=array();
  60. // 組み合わせの最大値
  61. $max_sum=0;
  62. // どの項目が最大ですか
  63. $max_one=0 ;
  65. for ($start=$k; $start>0;$start--){
  66. // 固定の $start 要素で構成される最大解を求めます
  67. $start_w_arr = getMaxCombination2($start);
  68. echo "$start 要素で構成される最大解を求めます: n";
  69. print_r($start_w_arr);
  70. echo "n";
  71. $sum=array_sum( $start_w_arr );
  72. // 注: $k- - は降順に並べられているため、同じ和を持つ $k の組み合わせが早いほど、が見つかると、それが大きいほど、つまりより良い解となるため、
  73. if($sum>$max_sum){
  74. $max_sum=$sum;
  75. $max_one=$k 以下になります。 -$start;
  76. }
  77. $k_w_result[]= $start_w_arr ;
  78. }
  79. return $k_w_result[$max_one];
  80. }
  82. // 配列 $rocks 内の指定された $start 要素の組み合わせを見つけます。要素は可能な限り大きいですが、指定された値 $w 以下です。配列は大きい順に並べ替えられています
  83. function getMaxCombination2($start) {
  84. //rocks
  85. global $rocks;
  86. //船が一度に積み込める石の最大数 Block
  87. global $k;
  88. // 船の最大積載量
  89. global $w;
  91. if(count($rocks)<$start){
  92. return array(0);
  93. }
  94. $c=count($rocks );
  95. // ループ コードの $start 層を含む関数を $start に基づいて生成し、それをインクルードしてこの関数を呼び出します
  96. if(!file_exists ( "$start.php")){
  97. $output_1="";
  98. $output_2='$sum=';
  99. $output_3='if($sum<=$w){ $arr=array(); ;
  100. $output_4='';
  101. for($i=0;$ i<$start;$i++){
  102. $output_1.='for($p'.$i.'='.$i.'; $p'.$i.'<$c-'.($ start-$i-1).';$p'.$i.'++){'."n";
  103. if($i> ;0){
  104. $output_2.='+';
  105. }
  106. $output_2.='$rocks[$p'.$i.']';
  107. $output_3.='$arr[]=$rocks[$ p'.$i.'];';
  108. $output_4.=' }';
  109. }
  110. $output_2.=';';
  111. $output_3.=' return $arr; }' ;
  112. $output='< ;?php 関数 myfor'.$start.'($rocks,$c ,$w){ '.$output_1.$output_2.$output_3.$output_4 .' } ?>';
  114. file_put_contents("$start .php",$output);
  115. include_once "$start.php";
  116. }
  117. else{
  118. include_once "$start.php";
  119. }
  120. return call_user_func('myfor'.$start ,$rocks,$c, $w);
  121. }
  123. //計算を開始します
  124. //最初に配列を大きいものから小さいものに並べ替えます。この操作は、後続のアルゴリズムで時間と労力を節約するための鍵です
  125. rsort($rocks);
  127. //石が大きすぎてボートが小さすぎる場合に、次のアルゴリズムが無限ループを引き起こすのを防ぎます
  128. foreach ($rocks as $v){
  129. if($v>$w){
  130. die("石を積んだ船で、また大きな船で戦いましょう！」 ");
  131. }
  132. }
  134. //アルゴリズム開始
  135. while(!empty($rocks)){
  136. // 船の積み込み開始
  137. $process[$count]=array();
  139. // 船の積み込み
  140. $process[$count]= getMaxCombination( ) ;
  142. // 出荷された
  143. をrocksから削除 foreach($process[$count] as $v){
  144. $key=array_search($v, $rocks) ;
  145. unset( $rocks[$key]);
  146. }
  147. $rocks=array_values($rocks);
  148. // 出荷数 + 1
  149. $count++;
  150. }
  151. // 出力結果
  152. echo '最小回数:' .$count. "n";
  154. echo '発送プロセス:';
  155. print_r($process);
  157. ?>
コードをコピー
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
前の記事：php eval バックドア プログラムを共有する次の記事：php eval バックドア プログラムを共有する

関連記事

続きを見る