/1 背包动态规划算法的空间优化是使用大小等于背包容量的一维数组（例如 A），并在每次迭代 i 时简单地覆盖 A[w]（如果需要），其中 A[w] 表示如果考虑前 i 项且背包容量为 w 时的总值。如果使用这种优化，有没有办法重建拣选的项目列表，也许通过在 DP 算法的每次迭代中保存一些额外的信息？例如，在贝尔曼福特算法中，可以实现类似的空间优化，只要我们保留前置指针的列表，即最后一个跃点（或第一个，取决于是否正在编写面向源/目标的算法），仍然可以重建最短路径。
作为参考，这是我使用动态规划对 0/1 背包问题的C++函数，其中我构造了一个二维向量 ans，使得 ans[i][j] 表示考虑前 i 项和背包容量 j 的总值。我通过反向遍历此向量来重建拾取的项目：
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;
}
以下是yildizkabaran答案的C++实现。它采用了 Hirschberg 聪明的分而治之的想法来计算背包实例的答案，该实例具有 n 个项目和容量 c，在 O（nc） 时间内，并且只有 O（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;
}
尽管这是一个老问题，但我最近遇到了同样的问题，所以我想我会在这里写我的解决方案。你需要的是赫希伯格的算法。尽管此算法是为重建编辑距离而编写的，但相同的原则也适用于此处。这个想法是，当搜索容量为 c 的 n 个项目时，在第一次扫描中确定对应于最终最大值的第 （n/2） 个项目的背包状态。让我们称这种状态为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） 完成，因此就 big-O 而言，即使算法至少慢两倍，也不会改变任何内容。我希望这对任何面临类似问题的人有所帮助。
据我了解，使用所提出的解决方案，实际上不可能获得某个客观值的涉及项目集。可以通过再次生成丢弃的行或维护合适的辅助数据结构来获取项目集。这可以通过将A中的每个条目与生成它的项列表相关联来完成。但是，这将需要比最初建议的解决方案更多的内存。本期刊还简要讨论了背包问题的回溯方法。