小编kab*_*bir的帖子

0/1 背包动态规划算法的空间优化是使用大小等于背包容量的一维数组（例如 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++) …

我查看了其他类似的问题,但无法找出导致此错误的原因.我正在编写一个C++程序来实现Kruskal的最小生成树算法,使用Union by rank with path compression.它正确打印MST的边缘,但包括路径压缩部分导致此错误:

*./kruskal'出错:free():无效指针:0x0000000001650d00*

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int,int> > pip;
typedef pair<int,int> pii;
class UnionFind {
    vector <int> parent,rank;
    public:
        UnionFind(int n){
            parent.resize(n);
            rank.resize(n);
            for (int i=0;i<n;i++) { //initialize all parents and ranks
                parent[i]=i;
                rank[i]=0;
            }
        }
        int find (int x){
            int root=x,y;
            while (parent[root]!=root) {
                root=parent[root];
            }
//uncommenting the following loop gives the error
            /*while (parent[x]!=root){ //path compression
                y=parent[x];
                parent[x]=root;
                x=y;
            }*/
            return root;
        }
        void unite (int …

找到给定的一组n个数的中值的方法是将它们分配到2个堆中.1是包含较低n/2(ceil(n/2))数的最大堆和包含其余数的最小堆.如果以这种方式维护,则中位数是第一个堆的最大值(如果n是偶数,则与第二个堆的最小值一起).这是我的c ++代码,它执行此操作:

priority_queue<int, vector<int> > left;
priority_queue<int,vector<int>, greater<int> > right;
cin>>n; //n= number of items
for (int i=0;i<n;i++) {
    cin>>a;
    if (left.empty())
        left.push(a);
    else if (left.size()<=right.size()) {
            if (a<=right.top())
                left.push(a);
            else {
                left.push(right.top());
                right.pop();
                right.push(a);
            }
    }
    else {
        if (a>=left.top())
            right.push(a);
        else {
            right.push(left.top());
            left.pop();
            left.push(a);
        }
    }
}

我们知道 heapify操作具有线性复杂性.这是否意味着如果我们将数字一个接一个地插入到上面的代码中的两个堆中,我们发现线性时间的中位数？