Off the top of my head I look at it as a graph 2 coloring problem. The graph starts out with 1 node per item and zero edges. If we think two items will be in th

Off the top of my head I look at it as a graph 2 coloring problem. The graph starts out with 1 node per item and zero edges. If we think two items will be in the same set (either in the knapsack or out) we merge the nodes and their weight and value combine into the new node. We draw edges between two nodes if their combined weights exceed the knapsack capacity. When we recurse out of our merge choice, we also draw an edge between the two nodes that composed the merge. Our recursion depth ends at a clique.