0/1背包证人生成

Question

我编写了一个背包类，用于求解背包算法。这个类工作并且正在使用动态规划算法来解决这个问题。

我在代码中实现了一些优化，所以我采用线性O(W)空间来寻找最大值，但是当我试图找到见证时，我仍然需要O(nW)空间来保存布尔表。

有人能告诉我是否有可能找到容量最大的背包的目击证人，其容量较小，复杂度为O(nW)，这里W是背包容量。

如果您认为代码中可能有更多的优化，也请告诉他们。

class Knapsack{
private:
  vector< int > value, weight, answer, DP;
  vector< bool > isin;
  int capacity;

public:
  Knapsack( vector< int > value, vector< int > weight, int capacity, bool needWitness ){
    this->value = value;
    this->weight = weight;
    this->capacity = capacity;

    this->answer.clear(); this->isin.clear(); this->DP.clear();
    this->DP.resize( capacity + 1, false );

    if ( needWitness ){
      this->isin.resize( value.size() * (capacity + 1), false );
      solveWithWitness();
    }
    else{
      solveWithoutWitness();
    }

  }

  void solveWithoutWitness(){
    for ( int i = 0; i < value.size(); i++ ){
      for ( int w = capacity; w >= weight[i]; w-- ){
        if ( DP[w] < value[i] + DP[w - weight[i]] ){
          DP[w] = value[i] + DP[w - weight[i]];
        }
      }
    }
  }

  void solveWithWitness(){
    for ( int i = 0; i < value.size(); i++ ){
      for ( int w = capacity; w >= weight[i]; w-- ){
        if ( DP[w] < value[i] + DP[w - weight[i]] ){
          DP[w] = value[i] + DP[w - weight[i]];
          isin[ i*capacity + w ] = true;
        }
      }
    }
    int position = value.size()-1;
    int w = capacity;
    while ( position >= 0 ){
      if ( isin[ position*capacity + w ] ){
        answer.push_back( position );
        w -= weight[position];
      }
      position--;
    }
  }


  vector< int > getWitness(){
    return this->answer;
  }

  int solution(){
    return DP[capacity];
  }

};

Answer 1

你在所有地方都使用O，所以我可以给你一个理论上的解决方案，它有点复杂和尴尬，仍然满足你想要的时间范围：

在n/2步骤中运行无见证DP；这告诉您只使用第一个n/2项就可以达到W中的哪个权重。现在，为剩下的n/2步骤运行一个DP，跟踪第一个n/2项到达每个单元所需的权重。

如果你天真地以递归的方式应用这个过程，你会得到一个类似于T(n，W) <= 2T(n/2，W) + O(nW)的时间递归，它的解是O(n log(n) W)。这还不够好。

但我们计算出了第一个n/2项目所需的重量。我们只需要关心DP数组的第一个w条目。因此，前半递归应该是T(n/2，w)时间，下半递归应该是T(n/2，W-w)时间，达到这个目标所需的工作需要O(nW)时间。

形式T(n，W) <= max(0 <= w <= W) T(n/2，w) + T(n/2，W-w) + O(nW)的递推解实际上是O(nW)。你可以直观地看到这一点，你可以想象一个n到W的矩形，最初的零。具有n‘项和权重W’的递归背包调用在某些n'-by-W‘子矩形中为每个条目添加1。然后递归的第一级加一个nW，第二级nW/2，第三个nW/4，等等，给出一个几何级数。