5 대 알고리즘 의 분지 정계 법

문제: 총 n 개의 컨테이너 에 2 척 의 적재량 이 각각 c1, c2 인 기선 을 실 어야 하 는데 그 중에서 컨테이너 i 의 무 게 는 wi 이 고 합 리 적 인 적재 방안 이 이 n 개의 컨테이너 를 이 2 척 의 기선 에 실 을 수 있 는 지 확인 해 야 한다.
추상: n 개의 물건 을 2 개의 용기 에 넣 고 모든 용기 가 중량 을 초과 해 서 는 안 되 며 실행 가능 한 방안 을 찾 습 니 다.
사고: 먼저 가능 한 한 첫 번 째 배 를 가득 채 운 다음 에 나머지 컨테이너 를 두 번 째 배 에 실 으 면 두 번 째 배 에 실 을 수 없 으 면 문제 가 풀 리 지 않 는 다.문 제 는 첫 배의 최대 적재량 을 구 하 는 것 으로 바 뀌 었 다.분기 정계 법 으로 공간 검색 을 진행 합 니 다.
코드 는 다음 과 같 습 니 다:

package test;
 
import java.util.LinkedList;
 
/**
 *            
 * 
 * @author yanghang
 *
 */
public class Fenzhidingjie {
 
    private static float[] w = { 40, 40, 10 }; //       
    private static int n = w.length; //     
    private static float c1 = 50; //         
    private static float c2 = 50; //         
 
    private static float bestw; //          
    private static float ew; //        
    private static LinkedList mq = new LinkedList(); // FIFO  
 
    /**
     *      
     * 
     * @param c
     */
    public static float maxLoading(float c) {
        mq.addLast(new Float(-1)); //        ，    
        int i = 0; // E-    
        ew = 0; //        
        bestw = 0; //       
 
        while (!mq.isEmpty()) { //        
            if (ew + w[i] <= c) { //   E-      ，  i      
                addLiveNode(ew + w[i], i); //   i    
            }
 
            addLiveNode(ew, i); //         ，     i
 
            ew = (Float) mq.removeFirst(); //       
 
            if (ew == -1) { //       
                if (mq.isEmpty()) {
                    return bestw;
                }
                mq.addLast(new Float(-1));
                ew = (Float) mq.removeFirst(); //       
                i++; // ew  
            }
        }
        return bestw;
    }
 
    /**
     *   
     * 
     * @param wt
     * @param i
     */
    public static void addLiveNode(float wt, int i) {
        if (i == n - 1) { //    0  ，   
            if (wt > bestw) {
                bestw = wt;
            }
        } else { //     
            mq.addLast(new Float(wt));
        }
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //          
        float s = 0;
        for (float f : w) {
            s += f;
        }
        if (s <= c1 || s <= c2) {
            System.out.println("need only one ship!");
        }
        if (s > c1 + c2) {
            System.out.println("no solution!");
            return;
        }
 
        float bestw = Fenzhidingjie.maxLoading(c1);
 
        if (s - bestw <= c2) {
            System.out.println("The first ship loading " + bestw);
            System.out.println("The second ship loading " + (s - bestw));
        } else {
            System.out.println("no solution!");
        }
 
    }
 
}