从空间优化的0/1背包实现重构项目列表

Question

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

作为参考，这里是我使用动态规划的0/1背包问题的C函数，其中我构造了一个二维向量ans，使得ans[I][j]表示考虑到前I项和背包容量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

据我所知，使用建议的解决方案，实际上不可能获得特定目标值的相关项目集。可以通过再次生成丢弃的行或维护适当的辅助数据结构来获得项目集。这可以通过将A中的每个条目与生成该条目的项目列表相关联来实现。然而，这将需要比最初提出的解决方案更多的内存。本文还简要讨论了背包问题的回溯方法。

Answer 2

虽然这是一个老问题，但我最近遇到了同样的问题，所以我想我应该在这里写下我的解决方案。你需要的是Hirschberg的算法。虽然此算法是为重建编辑距离而编写的，但这里也适用相同的原则。其思想是，当在容量c中搜索n个项目时，在第一次扫描中确定与最终最大值相对应的第（n/2）个项目的背包状态。让我们将此状态称为weight\u m和value\m。这可以通过跟踪大小为c的额外1d数组来实现。因此内存仍然是O（c）。然后将问题分为两部分：容量为weight\m的0到n/2项和容量为c-weight\m的n/2到n项。减少的问题总大小为nc/2。继续这种方法，我们可以确定每个项目后的背包状态（已占用重量和当前值），然后我们可以简单地检查哪些项目被包括在内。该算法在使用O（c）内存的情况下在O（2nc）中完成，因此就大O而言，即使算法的速度至少是原来的两倍，也不会发生任何变化。我希望这对任何面临类似问题的人都有帮助。

Answer 3

下面是yildizkabaran答案的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;
}