백트래킹 -(3) The 0-1 Knapsack Problem

The 0-1 Knapsack Problem

백트래킹으로 해결하기 

노드의 첫 번째 줄: 현재 가방에 들어온 물건들의 가치 합

           두 번째 줄: 현재 가방에 들어온 물건들의 무게 합

           세번째 줄: 현재 상태에서 최대 가치의 upper bound

          -> upper bound는 물건을 쪼갤 수 있다는 가정을 통해 얻을 수 있다

 

 

 

public static void knapsack(index i, int profit, int weight)
{
    if ( weight <= W && profit > maxProfit ) {
        maxProfit = profit ; //현재까지 최대이익
        numBest = i ;
        bestSet = include ;
    }
    if (promising(i)) {
        include[i+1] = “yes” ; //i+1번째 아이템 추가했다고 표시
        knapsack(i+1,profit+p[i+1],weight+w[i+1]);
        include[i+1] = “no” ;  //i+1번째 아이템 추가 안 했다고 표시
        knapsack(i+1,profit, weight);
    }
}



public static bool promising(index i) {
    index j,k ; int totWeight ; float bound ;
    if (weight >=W) //i번째 아이템 담고 더 이상 담을 수 없다면
    	return false ;
    else {
        j = i+1 ; //다음 아이템
        bound = profit ; totWeight = weight ; // 현재 이익,무게 상태에서 시작
        while ( j<=n && totWeight + w[j] <= W ) {
            totWeight = totWeight + w[j] ;
            bound = bound + p[j] ;
            j++ ;
    	}
        k = j ;
        if (k <= n) //한번에 담으면 무게가 넘칠 때 쪼개서 넣기
        	bound=bound+(W–totWeight)*p[k]/w[k]; //(더 담을 수 있는 무게)*단위 무게 당 가치 더하기
        return bound > maxProfit ; //maxProfit보다 높아야 계속 탐색
    }
}