if (promising ( )) v if (aSolutionAt( )) v write the solution else //expand the node for ( each child of ) u v ( ) checknode u Checknode Checknode uses the functions: which checks that the partial solution represented by can lead promising(v) v to the required solution which checks whether the partial solution represented by aSolutionAt(v) node solves the problem. v Sum of subsets when is a node – “promising”? Consider a node at depth i = weight of node, i.e., sum of numbers included in partial solution node weightSoFar represents = weight of the remaining items i+1 to n (for a node at depth i) totalPossibleLeft A node at depth i is non-promising if (weightSoFar + < S ) or totalPossibleLeft (weightSoFar + w[i+1] > S ) To be able to the must be sorted in non-decreasing wi use this “promising function” order
if (promising ( v )) if (aSolutionAt( v )) write the solution else //expand the node for ( each child u of v ) checknode ( u ) Checknode Checknode uses the functions: promising(v) which checks that the partial solution represented by v can lead to the required solution aSolutionAt(v) which checks whether the partial solution represented by node v solves the problem. Sum of subsets – when is a node “promising”? Consider a node at depth i weightSoFar = weight of node, i.e., sum of numbers included in partial solution node represents totalPossibleLeft = weight of the remaining items i+1 to n (for a node at depth i) A node at depth i is non-promising if (weightSoFar + totalPossibleLeft < S ) or (weightSoFar + w[i+1] > S ) To be able to use this “promising function” the wi must be sorted in non-decreasing order