항목을 4 개의 상자로 똑같이 나누는 방법은 무엇입니까?

Question

내가 다른 크기의 가방 인 을 가지고 있다고 가정합니다. 실제로 PHP 배열은이 데이터를 포함합니다.

Bag A 60 Kg 
Bag B 80 Kg 
Bag C 20 Kg 
Bag D 10 Kg 
Bag E 80 Kg 
Bag F 100 Kg 
Bag G 90 Kg 

PHP에서는이

Array 
(
    [30] => 60 
    [31] => 120 
    [32] => 120 
    [33] => 60 
    [35] => 180 
) 

모양을 지금은 동등하게이 무게를 균형을 4 용기의 모든 7 백를 분할해야합니다. 하지만 나는 무게를 관리하기 위해 가방을 부러 뜨릴 수 없습니다. 이 일을하는 방법을 권해주십시오. 어떻게 무게를 균형을 모든 가방을 배포 할 것입니다 수식 또는 php 함수를 작성할 수 있습니다. 용기 용량에는 제한이 없습니다. 또한 배급 후 모든 용기의 무게가 같을 필요는 없습니다. 로드 밸런싱 만하면됩니다. 미리 감사드립니다.

Answer 1

이 제품의 무게를 얻고 가방 번호를 반환하는 함수 만들기 - 아직도 들어갈만큼의 최소한의 여유 공간이 사람을. 가방에 넣어. 완료 될 때까지 반복하십시오.

$bags = array(60,80,20,10,80,100,90); 
$containers = array(1=>100,2=>100,3=>100,4=>100); // number -> free space 
$placement = array(); 

rsort($bags); // biggest first - usually it's better 

function bestContainerFor($weight) { 
    global $containers; 
    $rest = 0; 
    $out = 0; // in it won't change $weight fits nowhere 
    foreach($containers as $nr=>$space) { 
     if($space<$weight) continue; // not enough space 
     if($space-$weight<$rest) continue; // we have a better case 
     $rest = $space-$weight; 
     $out = $nr; 
    } 
    if($out) $containers[$out]-=$weight; // occupy the space 
    return $out; 
} 

foreach($bags as $nr=>$w) { 
    $p = bestContainerFor($w); 
    $placement[$nr] = $p; // for later use; in this example it's not needed 
    if($p) print "Bag $nr fits in $p<br>"; 
    if(!$p) print "Bag $nr fits nowhere<br>"; 
} 

테스트되지 않았습니다. 당신이 당신의 코드에 대한 세부 사항을 주면, 나는 적응하려고 노력할 것이다. 이것은 단지 그것의 원리를 보여줍니다.

• 이 변수 컨테이너 크기와 함께 작동, 그것은 당신에게 각각의 가방이 아닌 합계 중량의 위치를 ​​제공
• 는
는 동일한 분배에 대한 최적 아니다
• , 그냥 좋은를 제공

  하는 것으로 케이스

Answer 2

가방 무게의 합을 계산하여 컨테이너 수로 나눕니다. 그런 다음 빈 패키지 알고리즘을 사용하여 개별 컨테이너에 가방을 분배하십시오. 예 : 귀하의 배열에서 한 번에 하나의 가방을 가져다가 컨테이너의 무게 플러스 귀하의 가방의 무게가 최대 가능한 용기의 무게보다 적은 첫 번째 컨테이너에 넣어.

http://en.wikipedia.org/wiki/Bin_packing_problem

업데이트 : 루비로 작성 예. PHP에서 다시 작성하기가 어렵지 않아야합니다. 그것은 가방을 용기에 비교적 균등하게 분배합니다 (더 정확한 해결책이있을 수 있습니다).

# A list of bags with different weights 
list_of_bags = [11, 41, 31, 15, 15, 66, 67, 34, 20, 42, 22, 25] 
# total weight of all bags 
weight_of_bags = list_of_bags.inject(0) {|sum, i| sum + i} 
# how many containers do we have at our disposal? 
number_of_containers = 4 
# How much should one container weight? 
weight_per_container = weight_of_bags/number_of_containers 
# We make an array containing an empty array for each container 
containers = Array.new(number_of_containers){ |i| [] } 

# For each bag 
list_of_bags.each do |bag| 
    # we try to find the first container 
    containers.each do |container| 
     # where the weight of the container plus the weigth of the bag is 
     # less than the maximum allowed (weight_per_container) 
     if container.inject(0) {|sum, i| sum + i} + bag < weight_per_container 
      # if the current container has space for it we add the bag 
      # and go to the next one 
      container.push(bag) 
      break 
     end 
    end 
end 

# output all containers with the number of items and total weight 
containers.each_with_index do |container, index| 
    puts "container #{index} has #{container.length} items and weigths: #{container.inject(0) {|sum, i| sum + i}}" 
end 

예를 들어 결과 :

container 0 has 3 items and weigths: 83 
container 1 has 3 items and weigths: 96 
container 2 has 2 items and weigths: 87 
container 3 has 2 items and weigths: 76