Paradigms for Optimization Problems - A Concise and Practical Introduction to Programming Algorithms in Java - page 197

23571123=51
257911413=51
2541327=51
2711427=51
2941323=51
291327=51
3579423=51
357927=51
3571323=51
3591123=51
741327=51
911427=51
1141323=51
11 13 27 =51

Exhaustive search is not an effective algorithmic technique since it fully explores
the solution space to retrieve all potential solutions. The solution space is indeed
a very sparse subset, a tiny fraction of the configuration space. For example, we
found 14 solutions among a configuration space of size 2 10 = 1024. Furthermore,
note that if all object weights add up to less than the capacity weight, we can
obviously avoid performing the search since we already know that there is no
possible solution. Thus the plain implementation of exhaustive search does
extra work.
In order to avoid some of the unnecessary explorations, we can implement a cut
in recursive function solveKnapSack . Indeed, if at some stage of the recursion,
we already know that the current bag weight exceeds the capacity, it is not
worth adding other remaining objects that can only add weight to the bag. We
can therefore stop the recursion at these stages. To measure how many times
this cut was applied in practice, we add a static (class) variable initialized at
zero: static int nbCut=0; The exploration procedure with the cut now reads
as:

Program 9.4 Adding a cut to the recursive exhaustive search
static void solveKnapSack( boolean [] chosen , int goal , int i,
int total)
if (total > goal)
{ nbCut++;
return ; // cut recursive explorations
}
if ((i > =chosen . length)&&(total!=goal))
return ;
if ( total==goal)
{ display (chosen , goal) ; }
else
chosen [ i]= true ; // add item first and proceed
solveKnapSack(chosen , goal , i+1,total+weight [ i ]) ;
chosen [ i]= false ;

// and then remove it and proceed