Java에서 bruteforce를 사용하여 3D 배낭 해결

Question

3 차원 배낭 문제를 해결하고 싶습니다.

다른 너비, 높이, 길이 및 값을 가진 여러 상자가 있습니다. 나는 지정된 공간이 있고 그 공간에 상자를 넣어 최적의 이익을 얻을 것입니다. 나는 bruteforce를 사용하여 그것을하고 싶다.

저는 Java로 프로그래밍하고 있습니다.

public void solveBruteforce(double freeX, double freeY, double freeZ) { 
    for(int i = 0; i < numOfBoxes; i++) { 
     for(int j = 0; j < BoxObject.numOfVariations; j++) { 
     if(possible to place box) { 
      place(box); 
      add(value); 
      solveBruteforce(newX, newY, newZ); 
     } 
     } 
    } 
    remove(box); 
    remove(value); 
} 

하지만 각 줄은 y 및 z 다른 무료 X를 가지고 문제를 얻을 것이다 : 는 그래서, 재귀와 함께 할 것을 시도했다.

다른 방법으로 누군가 나를 찾을 수 있습니까?

Answer 1

첫 번째 것은 팔레트를 사용하여 공간에 물건이 어디에 있는지 추적합니다. Occupancy 트리는 모든 노드에서 점유 플래그가있는 3D 4 아웃도 트리로 공간을 검색 할 수있는 공간으로 나눕니다. 이것은 상자를 배치하기 위해 일종의 휴리스틱 검색을 사용하고 모든 가능성을 시도하는 경우에도 유용합니다. 금지 된 (붐비는) 게재 위치 바로 가기가 가능합니다.

브 루트 포스는 길이가입니다. 그러나 이것이 원하는 경우 게재 위치의 순열을 시험하기위한 순서를 정의해야합니다.

많은 반복이 필요하므로 스택 오버플로가 발생하므로 재귀가 그리 좋지 않습니다.

첫 번째 초안 대안은 탐욕스러운 알고리즘을 포함 할 것이다. 이익을 극대화하는 상자를 가져 와서 가장 큰 상자를 가져 와서 가장 큰 상자를 가져 와서 가장 적합한 상자를 찾습니다. 있는 조치를 존중, # {공간} 가능성에서 # {상자} 슬롯을 선택하는 생각의 편곡을 정의하는 방법에 대한 아이디어를 들어

def maximize_profit(boxes,space): 
    max_profit = 0 
    best_fits = list() 
    while(Arranger.hasNext()): 
     a_fit,a_profit = Arranger.next(boxes,space) 
     if (a_profit == max_profit): 
      best_fits.append(a_fit) 
     elif (a_profit > max_profit): 
      max_profit = a_profit 
      best_fits = [ a_profit ] 
    return best_fits, max_profit 

:

그러나, 당신은 모든 가능한 조합을 원했고 말 동일한 wrt 대칭. 대안으로 "홍수 채우기"방법으로 아이디어를 얻을 수 있습니다.