PHP는 복싱 문제를 해결합니다

포장 문제와 돌 교차 문제
에 대한 나의 해결책은 http://www.oschina.net/question/117304_112681에서 찾을 수 있습니다

구현을 위한 주요 아이디어는 다음과 같습니다.
1. 돌은 우선 포장해야 함 (조리 포장하거나 나중으로 미루기, 먼저 해결)
2. w에 가까운 무게로 포장 우선
3. 9개 등 같은 무게의 여러 개 포장 우선 6과 9,5,1 비율이면 951 패킹을 우선으로 합니다
4. PHP 함수를 사용하여 코드를 단순화하고, k 값을 기반으로 함수를 생성하는 기술을 사용합니다
5. 이러한 유형의 문제는 계산량이 크므로 재량에 따라 테스트용 매개변수를 설정하십시오.

출력 예: (rocks가 1~9일 때, w는 15, k는 3)
3개 요소로 구성된 최대 해 찾기:
Array
(
[ 0 ] => 9
[1] => 5
[2] => 1
)

2개의 요소로 구성된 최대 해를 구합니다:
배열
(
[0] => 9
[1] => 6
)

1개의 요소로 구성된 최대 솔루션 찾기:
배열
(
[0] => 9
)

3개 요소로 구성된 최대 솔루션 찾기:
배열
(
[0] => 8
[1] = > 4
[2] => 3
)

2개 요소로 구성된 최대 솔루션 찾기:
배열
(
[0] => 8
[1] = > 7
)

1개의 요소로 구성된 최대 솔루션 찾기:
배열
(
[0] => 8
)

3개 요소로 구성된 최대 솔루션:
배열
(
[0] => 7
[1] => 6
[2] => 2
)

2개 요소로 구성된 최대값 찾기:
배열
(
[0] => 7
[1] => 6
)

최대값 찾기 1개 요소로 구성된 솔루션:
Array
(
[0] => 7
)

최소 횟수: 3
조립 선박 공정: Array
(
[0] => 배열
(
[0] => 9
[1] => 5
[2] => 1
)

[1] => 배열
(
[0] => 8
[1] => 4
[2] => 3
)

[2 ] => 배열
(
[0] => 7
[1] => 6
[2] => 2
)

)

// php 운동 복싱 문제
// 작성자: mx (http://my.oschina.net/meikaiyuan)
/ / 2013/5/30

// 질문:
// http://www.oschina.net/question/117304_112681
/*
제목:

 이전에도 비슷한 질문이 있었지만 좋은 답변이 없었습니다. 그래서 다시 묻고 싶습니다.

배를 타고 강 건너편으로 끌어야 할 크고 작은 돌무더기가 있습니다
--m개의 돌이 있고 각 돌의 무게를 알 수 있습니다
--배는 한 번에 k개의 돌만 실을 수 있고, 선적 무게는 w를 초과할 수 없습니다.
--모든 돌을 강 건너편으로 운반할 수 있는 최소 이동 횟수를 찾고 싶습니다.

 ---------------------------
예시 1
 돌은 9개가 있고, 무게는 1, 2, 3, 4, 5, 6, 7, 8, 9
k=3
w=15
결과는 최소 3번 이상 운송할 수 있습니다.
 ----------
 예시 2
 9개가 있습니다 돌 블록의 무게는 1,1,1,5,6,6,7,9,9
k=3
w=15
결과적으로 최소 4번의 시간이 소요됩니다. 그것을 운반하십시오.
*/

//코드 시작

//Stones
global $rocks;
//배가 한 번에 적재할 수 있는 최대 조각 수
global $k;
//선박의 최대 적재 용량
global $w;

$k=3;
$rocks=array(1,2,3,4, 5,6,7,8 ,9);
// $rocks=array(1,1,1,5,6,6,7,9,9) //이 데이터 세트로 결과를 시험해 보세요. ?
$w=15;

// 지금까지 몇번 발송되었는지
$count=0;
// 운송 과정, 2차원 배열, 형태로 1=>array(9 ,5,1), 어떤 항목이 여러 번 실행되었는지 나타냅니다.
$process=array();

// $rocks 배열에서 다음과 같은 조합을 찾습니다. 최대 $k개의 요소와 합계가 가능한 한 크지만 지정된 값 $w보다 작거나 같습니다. 배열은 큰 것에서 작은 것 순으로 정렬되었습니다.
function getMaxCombination( ) {
 //Stones
 global $rocks;
 // 매번 배송 최대 적재 가능 개수
 global $k;
 // 선박의 최대 적재 용량
 global $w;

 // 모든 요소의 합이 w 및 가장 큰 집합보다 작거나 같도록 다양한 $k를 저장합니다.
 $k_w_result=array();
 // 최대 결합 값
 $max_sum =0;
 // 가장 큰 항목은 무엇입니까
 $max_one=0;

 for ($start=$k;$start>0;$start--){
 / / 고정된 $start 요소로 구성된 최대 해 찾기
 $start_w_arr = getMaxCombination2($start);
 echo "$start 요소로 구성된 최대 해 찾기: n";
 print_r($start_w_arr);
 echo "n";
 $sum=array_sum( $start_w_arr );
 / / 참고: 내림차순으로 정렬되므로 $k--, 같은 합계를 갖는 조합 $k가 빠를수록 발견되면 클수록, 즉 해가 더 좋아지기 때문에
 if($sum>$max_sum) {
 $max_sum=$sum; $max_one=$k-$start;
 }
 $k_w_result[]= $start_w_arr ;
 }
 return $k_w_result[$max_one ];
}

// $rocks 배열에서 주어진 $start 요소의 조합을 찾습니다. 이 요소의 합은 가능한 한 크지만 지정된 값 $w보다 작거나 같습니다. 배열은 큰 것에서 작은 것으로 정렬되었습니다. 🎜>function getMaxCombination2($start) {
 //암석
 global $rocks;
 //선박이 한 번에 적재할 수 있는 최대 암석 수
 global $k;
 // 선박의 최대 적재 용량
 global $w;

 if(count($rocks)<$start){
 return array(0);
 }
 $ c=count($rocks);
 // 루프 코드에 대한 $start 레이어를 포함하는 $start를 기반으로 함수를 생성한 다음 이를 포함하고 이 함수를 호출합니다.
 if(!file_exists( "$start. php" )){
 $output_1="";
 $output_2='$sum=';
 $output_3='if($sum<=$w){ $arr=array(); ';
 $output_4='';
 for($i=0;$i<$start;$i ){
 $output_1.='for($p'.$i.'= '.$i.';$p'.$i.'<$c-'.($start-$i-1).';$p'.$i.' ){'."n";
 if($i>0){
 $output_2.=' ';
 }
 $output_2.='$rocks[$p'.$i.']';
 $output_3 .='$arr[]=$rocks[$p'.$i.'];';
 $output_4.='}';
 }
 $output_2.=';' ;
 $output_3.=' $arr 반환 }' ;
 $output='';

 file_put_contents("$start.php",$output);
 include_once "$start.php";
 }
 else{
 include_once "$start.php";
 }
 return call_user_func('myfor'.$start ,$rocks,$c,$w);
}

//계산 시작
// 먼저 배열을 큰 것에서 작은 것 순으로 정렬합니다. 이 작업은 후속 알고리즘에서 시간과 노력을 절약하는 열쇠입니다
rsort($rocks);

// 바위가 지나가는 것을 방지하기 위해 대형 선박이 너무 작아서 다음 알고리즘의 무한 루프가 발생합니다.
foreach ($rocks as $v){
 if($v>$w) {
 die("돌이 있으면 배에 실을 수 없습니다. 더 큰 배로 바꿔서 다시 싸워보세요! ");
 }
}

// 알고리즘 시작
while(!empty($rocks)){
 // 선박 선적 시작
 $process[$ count]=array();

 // 배송
 $process[$count]= getMaxCombination( ) ;

 // 이미 배송된 foreach($ 프로세스[$count]를 $v){
 $key=array_search($v, $rocks);
 unset( $rocks[$key]);
 }
 $ Rocks=array_values( $rocks);
 // 배송 횟수 1
 $count ;
}
// 출력 결과
echo '최소 횟수:'.$count."n" ;

echo '배송 과정:';
print_r($process);

?>


코드 복사