private void knapsack ( int bin , int d ) throws ContradictionException { final int maxLoad = prop . loads [ d ] [ bin ] . getUB ( ) ; final int free = maxLoad - prop . assignedLoad [ d ] [ bin ] . get ( ) ; if ( free >= dynBiggest [ d ] [ bin ] . get ( ) ) { // fail fast. The remaining space > the biggest item. return ; } if ( free > 0 ) { // The bin is not full and some items exceeds the remaining space. We // get rid of them // In parallel, we set the new biggest candidate item for that // (bin,dimension) int newMax = - 1 ; for ( int i = candidate . get ( bin ) . nextSetBit ( 0 ) ; i >= 0 ; i = candidate . get ( bin ) . nextSetBit ( i + 1 ) ) { if ( prop . iSizes [ d ] [ i ] > free ) { if ( prop . bins [ i ] . removeValue ( bin , prop ) ) { prop . removeItem ( i , bin ) ; if ( prop . bins [ i ] . isInstantiated ( ) ) { prop . assignItem ( i , prop . bins [ i ] . getValue ( ) ) ; } } } else { // The item is still a candidate, we just update the biggest value. newMax = Math . max ( newMax , prop . iSizes [ d ] [ i ] ) ; } } dynBiggest [ d ] [ bin ] . set ( newMax ) ; } }
Propagate a knapsack on a given dimension and bin . If the usage of an item exceeds the bin free capacity it is filtered out .