Thursday, July 24, 2014

Subset sum problem (Simplified Knapsack) - I

Problem Definition

Given target 't', and a collection of positive integers w1, w2, w3, ..., wn, determine whether there is some selection among the weights so that the total is exactly 't'.
For ex, if t = 10, and the weights are 7, 5, 4, 4, and 1, then the answer is - yes there is selection 5, 4, 1 whose some is '10'

Brute Force

One obvious solution is going through all the subsets of given set of weights, and see if there is any combination that sums up to given total. As we all know set of 'n' elements will have up-to 2^n subsets - which are nothing but no. of combinations. So, the algorithm will be exponential. 

Basic gist of the below algorithm is that either item contributes to get to given target 't' or not. So, initially it assumes that the item contributes to get to the given target, and see if rest of the components can contribute to remaining weight. If it is not possible then it checks for the other possibility that the item doesn't contribute to get to the given target, and see if the remaining elements can form the target.

Code Snippet
  1. private bool KnapsackSimplifiedProblemRecursive(int[] weights, int sum, int currentSum, int index, List<int> itemsInTheKnapsack)
  2.         {
  3.             if (currentSum == sum)
  4.             {
  5.                 return true;
  6.             }
  7.             if (currentSum > sum)
  8.             {
  9.                 return false;
  10.             }
  11.             if (index >= weights.Length)
  12.             {
  13.                 return false;
  14.             }
  15.             itemsInTheKnapsack.Add(weights[index]);
  16.             bool flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: currentSum + weights[index],
  17.                 index: index + 1, itemsInTheKnapsack: itemsInTheKnapsack);
  18.             if (!flag)
  19.             {
  20.                 itemsInTheKnapsack.Remove(weights[index]);
  21.                 flag = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum, index + 1, itemsInTheKnapsack);
  22.             }
  23.             return flag;
  24.         }

Basically above private method will be invoked by the following public method.

Code Snippet
  1. public bool KnapsackRecursive(int[] weights, int sum, out List<int> knapsack)
  2.         {
  3.             if(sum <= 0)
  4.             {
  5.                 throw new ArgumentException("sum should be +ve non zero integer");
  6.             }
  7.             knapsack = new List<int>();
  8.             bool fits = KnapsackSimplifiedProblemRecursive(weights, sum, currentSum: 0, index: 0,
  9.                 itemsInTheKnapsack: knapsack);
  10.             return fits;
  11.         }

Time Complexity

Another way to prove that above algorithm is exponential is by considering worst case. Assume that the given target cannot be achieved by the given weights. That means, it essentially go through all combinations which is clearly exponential.

Removing tail recursion

Tail recursion means, at the end of the method typically there will be just recursive call. typically these can be removed either with using a stack or goto statements. Below is the version of removing tail recursion using stack:
 
Code Snippet
  1. public bool SubsetSum_NoRepetition_KnapsackSimplifiedProblemIterativeUsingStack(int[] weights, int sum, out List<int> knapsack)
  2.         {
  3.             this.Validate(weights, sum);
  4.             var knapsackIndices = new List<int>();
  5.             knapsack = new List<int>();
  6.             Stack<SubsetSum_NoRepetition_KnapsackStackNode> stack = new Stack<SubsetSum_NoRepetition_KnapsackStackNode>();
  7.             stack.Push(new SubsetSum_NoRepetition_KnapsackStackNode() { sumOfWeightsInTheKnapsack = 0, nextItemIndex = 1 });
  8.             stack.Push(new SubsetSum_NoRepetition_KnapsackStackNode() { sumOfWeightsInTheKnapsack = weights[0], nextItemIndex = 1, includesItemAtCurrentIndex = true });
  9.             knapsackIndices.Add(0);
  10.  
  11.             while (stack.Count > 0)
  12.             {
  13.                 var top = stack.Peek();
  14.                 if (top.sumOfWeightsInTheKnapsack == sum)
  15.                 {
  16.                     int count = 0;
  17.                     foreach (var index in knapsackIndices)
  18.                     {
  19.                         var w = weights[index];
  20.                         knapsack.Add(w);
  21.                         count += w;
  22.                     }
  23.                     Debug.Assert(count == sum);
  24.                     return true;
  25.                 }
  26.                 //basically either of the below three cases, we dont need to traverse/explore adjuscent
  27.                 // nodes further
  28.                 if ((top.nextItemIndex == weights.Length) //we reached end, no need to traverse
  29.                     || (top.sumOfWeightsInTheKnapsack > sum) // last added node should not be there
  30.                     || (top.alreadyExploredAdjuscentItems)) //already visted
  31.                 {
  32.                     if (top.includesItemAtCurrentIndex)
  33.                     {
  34.                         Debug.Assert(knapsackIndices.Contains(top.nextItemIndex - 1));
  35.                         knapsackIndices.Remove(top.nextItemIndex - 1);
  36.                     }
  37.                     stack.Pop();
  38.                     continue;
  39.                 }
  40.  
  41.                 var node1 = new SubsetSum_NoRepetition_KnapsackStackNode();
  42.                 node1.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack;
  43.                 node1.nextItemIndex = top.nextItemIndex + 1;
  44.                 stack.Push(node1);
  45.  
  46.                 var node2 = new SubsetSum_NoRepetition_KnapsackStackNode();
  47.                 knapsackIndices.Add(top.nextItemIndex);
  48.                 node2.sumOfWeightsInTheKnapsack = top.sumOfWeightsInTheKnapsack + weights[top.nextItemIndex];
  49.                 node2.nextItemIndex = top.nextItemIndex + 1;
  50.                 node2.includesItemAtCurrentIndex = true;
  51.                 stack.Push(node2);
  52.  
  53.                 top.alreadyExploredAdjuscentItems = true;
  54.             }
  55.             return false;
  56.         }
  57.         class SubsetSum_NoRepetition_KnapsackStackNode
  58.         {
  59.             public int sumOfWeightsInTheKnapsack;
  60.             public int nextItemIndex;
  61.             public bool alreadyExploredAdjuscentItems;
  62.             public bool includesItemAtCurrentIndex;
  63.         }
 

Reference(s)

Posted by at
Labels: