java - 使用堆栈且无递归的深度优先背包

Question

我需要解决 Knapsack problem使用深度优先和堆栈，没有递归调用。我使用列表和递归解决了这个问题。我不知道如何使用堆栈而不是递归来解决问题。

这是我现在拥有的:

   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 保存元素的价格和重量。

Answer 1

你需要的是自己维护堆栈。在堆栈(或堆栈)中，您需要保留函数调用参数和局部变量(您还需要减少它们的数量)。从您的代码中不清楚您的背包语句是否允许携带多个相同类型的元素。所以我假设它是被禁止的(重写代码很容易，但事实并非如此)。在 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;
    }

注意:我想您知道仅仅消除递归并不能显着提高性能。只要此解决方案是蛮力且具有指数复杂度。对于不是很大的整数权重(价格)，有很好的动态规划解决方案，它采用多项式取决于项目数量和最大重量(最大价格上限)。