Depth first knapsack using stack and no recursion

Question

I need to solve the Knapsack problem using depth first and stacks with no recursive calls. I solved the problem using a list and recursion. I have no clue of how to solve the problem using stacks and no recursion.

This is what I have right now:

   private int knapsackDepthFirst(List<KnapsackObject> list, int weight, int price, int maxWeight) {
      if (list.size() == 0) return price;
      int max = Integer.MIN_VALUE;
      for (KnapsackObject item : list) {
         int best;
         if (weight + item.getWeight() > maxWeight) {
            best = Integer.MIN_VALUE;
         } else if (weight + item.getWeight() == maxWeight) {
            best = price + item.getPrice();
         } else {
            best = knapsackDepthFirst(list.subList(1, list.size()), weight + item.getWeight(), price + item.getPrice(), maxWeight);
         }
         if (best > max) max = best;
      }
      return max;
   }

KnapsackObject holds the price and weight of an item.

Answer 1

What you need is to maintain stack yourself. In stack (or stacks) you need to keep function call parameters, and local variable (you also need to reduce their count). It's not very clear from your code whether in your knapsack statement allowed to take multiple items of same type. So I assume that it's forbidden (It's easy to rewrite code it's not true). Check out following solution in c#:

    public class KnapsackObject
    {
        public int weight;
        public int price;
    }

    public static Int32 KnapsackSolve(int maxWeight, List<KnapsackObject> items)
    {
        Int32 max = Int32.MinValue;
        Int32 count = items.Count;
        // Its actually a stack contains a weight parameter for current iteration.
        Int32[] weights = new Int32[count + 2];
        // Its actually a stack contains a price parameter for current iteration.
        Int32[] prices = new Int32[count + 2];
        // Its actually a stack contains a flag which specify whether we already try to get item steps[current] of not.
        // If it's allowed to get multiple item of same type, it must be store index variable (int) instead of bool flag.
        Boolean[] itemGetted = new Boolean[count + 2];
        // Indicates that we need to leave current iteration when back track to it.
        Boolean[] finishIteration = new Boolean[count + 2];
        // Represents depth of current iteration.
        Int32 current = 0;

        // Put the first "call" into stack. Current weight = 0, price = 0.
        weights[current] = 0;
        prices[current] = 0;
        itemGetted[current] = false;
        finishIteration[current] = false;

        while (current >= 0)
        {
            // we already have done everything here, back tracking.
            if (finishIteration[current])
            {
                // Pop current call from stack.
                --current;
                continue;
            }

            // we already make our decision about all item types. 
            // Compare and back track.
            if (current == count)
            {
                if (max < prices[current])
                    max = prices[current];
                // Pop current call from stack.
                --current;
                continue;
            }

            // if we haven't tried to get current item
            if (!itemGetted[current])
            {
                itemGetted[current] = true;
                // and we can put it in knapack, try it.
                if (weights[current] + items[current].weight <= maxWeight)
                {
                    weights[current + 1] = weights[current] + items[current].weight;
                    prices[current + 1] = prices[current] + items[current].price;
                    itemGetted[current + 1] = false;
                    finishIteration[current + 1] = false;
                    // Push new call into stack.
                    current++;
                    continue;
                }
            }

            // and try not to put current item. 
            finishIteration[current] = true;
            weights[current + 1] = weights[current];
            prices[current + 1] = prices[current];
            itemGetted[current + 1] = false;
            finishIteration[current + 1] = false;
            // Push new call into stack.
            current++;
        }

        return max;
    }

Note: I suppose you know that just eliminate recursion doesn't improve performance too much. As soon as this solution is brute force and has exponential complexity. For not very big and integer weights (prices) there are good dynamic programming solutions which take polynomial depends on items count and max weight (max price upper bound).