从空间优化的0/1背包实现中重构物品列表

Question

使用1维数组（如A）进行空间优化的0/1背包动态规划算法，其大小等于背包容量，并在每次迭代i时仅覆盖A [w]（如果需要），其中A [w]表示考虑前i个项目并且背包容量为w时的总价值。

如果使用此优化，是否有一种方式可以重构选定的物品列表，例如在Bellman Ford算法中可以实现类似的空间优化，并且只要我们保留前任指针的列表，即最后一跳（或第一跳，具体取决于是编写源/目标导向算法）就可以重构最短路径。

以下是我的C++函数，用于使用动态规划解决0/1背包问题，我构建了一个2维向量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;
}

- kabir

---

我有点困惑这个问题；你描述了一个一维状态空间 A，但实现使用了一个二维状态空间 ans？所以，基本上 space_optimized 实现也使用了 ans，但是会丢弃较小的 i 值的行？ - Codor

@Codor 对的，我只是展示了如何从二维向量重构项目列表。如果是一维向量，我不知道该怎么做。 但是，使用这个一维向量计算总值很简单，我们只需要使用ans[x]而不是ans[i][x]，并且不断覆盖ans[x]即可。如果不包括项目i，则对于迭代ans[x]保持不变，否则我们将其替换为ans[i]+v[i-1]。 - kabir

在您的DP计算中，请在||条件的另一半之前测试x<w[i-1]，以便短路运算将防止ans[i-1][x-w[i-1]]尝试访问负索引处的数组元素，从而可能导致崩溃。 - j_random_hacker

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;
}

- j_random_hacker

Answer 2

即使这是一个旧问题，但最近我遇到了同样的问题，所以我想在这里写下我的解决方案。你需要的是Hirschberg算法。虽然这个算法是为了重建编辑距离而编写的，但是相同的原则也适用于此处。思路是当在容量c中搜索n个物品时，在第一次扫描中确定与最终最大值对应的(n/2)th项的背包状态。我们将其称为weight_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方面没有任何改变，即使算法至少慢了两倍。希望这对面临类似问题的人有所帮助。

- yildizkabaran

---

被低估的答案！我认为更准确的说法是，我们最初在O(nc)时间和O(c)空间内找到了两个半大小问题（前n/2个项目和后n/2个项目）的最优成本向量c1、c2和相应的前任向量p1、p2。向量和c1+reverse(c2)中的每个条目都是整个问题的某些解决方案的成本。如果在索引i处有一个最大值，则（1）c1[i]+c2[n-i]是整个问题的某个最优解的成本，且（2）此解决方案包括项目p1[i]和p2[n-i]。现在对这两个部分进行递归处理。 - j_random_hacker

Answer 3

据我了解，使用所提出的解决方案，对于特定目标值，获取涉及的项目集合实际上是不可能的。可以通过重新生成被丢弃的行或维护适当的辅助数据结构来获取项目集合。这可以通过将 A 中的每个条目与生成它的项目列表相关联来实现。然而，这将需要比最初提出的解决方案更多的内存。关于背包问题的回溯方法也在 this 期刊论文中简要讨论。

- Codor