algorithm - 从空间优化的 0/1 背包实现中重建项目列表

Question

0/1 背包动态规划算法的空间优化是使用大小等于背包容量的一维数组(比如 A)，并在每次迭代时简单地覆盖 A[w](如果需要) i，其中 A[w] 表示如果考虑前 i 项并且背包容量为 w 的总值(value)。如果使用这种优化，是否有一种方法可以重建选择的项目列表，也许通过在 DP 算法的每次迭代中保存一些额外的信息？例如，在 Bellman Ford 算法中，可以实现类似的空间优化，只要我们保留前导指针列表，即最后一跳(或第一跳，取决于源/正在编写面向目的地的算法)。

作为引用，这是我使用动态规划解决 0/1 背包问题的 C++ 函数，其中我构造了一个二维向量 ans，使得 ans[i][j] 表示考虑第 i 个项目和背包的总值(value)容量 j。我通过反向遍历这个向量 ans 来重建选取的项目:

void knapsack(vector<int> v,vector<int>w,int cap){
 //v[i]=value of item i-1
 //w[i]=weight of item i-1, cap=knapsack capacity
 //ans[i][j]=total value if considering 1st i items and capacity j
 vector <vector<int> > ans(v.size()+1,vector<int>(cap+1));

 //value with 0 items is 0
 ans[0]=vector<int>(cap+1,0);

 //value with 0 capacity is 0
 for (uint i=1;i<v.size()+1;i++){
    ans[i][0]=0;
 }

 //dp
 for (uint i=1;i<v.size()+1;i++) {
    for (int x=1;x<cap+1;x++) {
        if (ans[i-1][x]>=ans[i-1][x-w[i-1]]+v[i-1]||x<w[i-1])
            ans[i][x]=ans[i-1][x];
        else {
            ans[i][x]=ans[i-1][x-w[i-1]]+v[i-1];
        }
    }
 }
 cout<<"Total value: "<<ans[v.size()][cap]<<endl;

 //reconstruction
 cout<<"Items to carry: \n";
 for (uint i=v.size();i>0;i--) {
    for (int x=cap;x>0;x--) {
        if (ans[i][x]==ans[i-1][x]) //item i not in knapsack
            break;
        else if (ans[i][x]==ans[i-1][x-w[i-1]]+v[i-1]) { //item i in knapsack
            cap-=w[i-1];
            cout<<i<<"("<<v[i-1]<<"), ";
            break;
        }
    }
 }
 cout<<endl;
}

Answer 1

以下是 yildizkabaran's answer 的 C++ 实现.它采用 Hirschberg 巧妙的分而治之思想，在 O(nc) 时间和仅 O(c) 空间中计算具有 n 项和容量 c 的背包实例的答案:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Returns a vector of (cost, elem) pairs.
vector<pair<int, int>> optimal_cost(vector<int> const& v, vector<int> const& w, int cap) {
    vector<pair<int, int>> dp(cap + 1, { 0, -1 });

    for (int i = 0; i < size(v); ++i) {
        for (int j = cap; j >= 0; --j) {
            if (w[i] <= j && dp[j].first < dp[j - w[i]].first + v[i]) {
                dp[j] = { dp[j - w[i]].first + v[i], i };
            }
        }
    }

    return dp;
}

// Returns a vector of item labels corresponding to an optimal solution, in increasing order.
vector<int> knapsack_hirschberg(vector<int> const& v, vector<int> const& w, int cap, int offset = 0) {
    if (empty(v)) {
        return {};
    }

    int mid = size(v) / 2;
    auto subSol1 = optimal_cost(vector<int>(begin(v), begin(v) + mid), vector<int>(begin(w), begin(w) + mid), cap);
    auto subSol2 = optimal_cost(vector<int>(begin(v) + mid, end(v)), vector<int>(begin(w) + mid, end(w)), cap);

    pair<int, int> best = { -1, -1 };
    for (int i = 0; i <= cap; ++i) {
        best = max(best, { subSol1[i].first + subSol2[cap - i].first, i });
    }

    vector<int> solution;
    if (subSol1[best.second].second != -1) {
        int iChosen = subSol1[best.second].second;
        solution = knapsack_hirschberg(vector<int>(begin(v), begin(v) + iChosen), vector<int>(begin(w), begin(w) + iChosen), best.second - w[iChosen], offset);
        solution.push_back(subSol1[best.second].second + offset);
    }
    if (subSol2[cap - best.second].second != -1) {
        int iChosen = mid + subSol2[cap - best.second].second;
        auto subSolution = knapsack_hirschberg(vector<int>(begin(v) + mid, begin(v) + iChosen), vector<int>(begin(w) + mid, begin(w) + iChosen), cap - best.second - w[iChosen], offset + mid);
        copy(begin(subSolution), end(subSolution), back_inserter(solution));
        solution.push_back(iChosen + offset);
    }

    return solution;
}