时间戳

首页 > 解决方案 > 子集总和，带有回溯和类

c++ - 子集总和，带有回溯和类

问题描述

给定一个整数序列和一个数字，程序必须说明该序列中是否有任何组合对该数字求和。例如：

输入：1 2 3 4 5 # 6 输出：真（因为 1+5 = 6，或 2 + 4 = 6，或 1 + 2 + 3 = 6）。

找到什么解决方案并不重要，只要有解决方案。

输入：1 2 3 4 5 # 100 输出：假。这些数字的总和都不等于 100。

现在，输入：

243 5 35 24 412 325 346 24 243 432 # 1000

我越来越

main: malloc.c:2401: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed.

当它应该说假的时候。我必须使用 3 节课。求解器、解决方案和候选者。

Solver 只是调用回溯方法。解决方案有一个可能的解决方案。Candidat 具有正在查看的序列号的索引。

我不明白如何使用解决方案类的整数 _lvl 来移动不同的候选人。类求解器是正确的。错误必须在解决方案类和候选中。

我的问题是，我必须如何使用候选人和 _lvl 来检查可能的解决方案？我应该如何在解决方案类中实现以下方法？：Acceptable、complet、annotate、desanotate。

我得到错误的答案和 out_of_ranges 错误。

class solver
{
public:

    solver();

    bool solve(const solution &initial);

    solucio getSolution() const;

private:

    void findASolution();

    bool _found;

    solution _sol;
 };

求解器.cpp

bool solver::solve(const solution &initial)
{
    _found = false;
    _sol = initial;
    findASolution();
    return (_found);
}


void solver::findASolution()
{
    candidat iCan = _sol.inicializateCandidats();
    while ((not iCan.isEnd()) and (!_found))
    {
        if (_sol.acceptable(iCan)) {
            _sol.anotate(iCan);
            if(not _sol.complet()) {
                findASolution();
                if (!_found) {
                    _sol.desanotate(iCan);
                }
            }
            else {
                _found = true;
            }
        }
        iCan.next();
    }
}

这个类应该是正确的。我在课堂解决方案和候选人方面遇到了麻烦。类解决方案有 5 个重要方法：Acceptable、Complet、initializateCandidates()、annotate 和 desanotate。

如果候选人可以成为解决方案的一部分，则可接受为真。如果找到解决方案，则完成。注释以保存可能的候选人。去除不再是解决方案一部分的候选者。incializateCandidates 调用候选构造函数。

    solution();

    solution(const int sequence[], const int &n, const int &sum) {
        _searchedSum = sum;
        _n = n;
        _sum = 0;
        _lvl = 0;
        reserve(); // bad_alloc. Makes space for vectors
        for (int i = 0; i < n; i++) {
            _sequence[i] = sequence[i];
            _candidates[i] = - 1;
        }

    solution(const solution &o);

    ~solution();

    solution & operator=(const solution &o);

    candidat inicializateCandidats() const {
        return candidat(_n);
    }

    bool acceptable(const candidat &iCan) const {
        return (_sum + _sequence[iCan.actual()] <= _searchedSum);
    }

    bool complet() const {
         return (_sum == _searchedSum);
    }

    void show() const;

    void anotate(const candidat &iCan) {
        _niv++;
        _candidates[_niv] = iCan.actual();
        _sum += _sequence[iCan.actual()];
    }

    void desanotate(const candidat &iCan) {
        _candidates[_niv] = - 1;
        _sum -= _sequence[iCan.actual()];
        _niv--;
   }

private:

    // memory gestion methods
    void solution::reserve() {
        _sequence = new int[_n];
        _candidates = new int[_n];
    }

    int *_sequence; // original sequence
    int *_candidates; // possible subsequence part of solution
    int _n; // size of the array
    int _lvl; // lvl of the tree generated by backtracking
    int _searchedSum; 
    int _sum; // total sum of actual solution

还有班级候选人，这只是一个柜台。没有其他的。

candidat::candidat(const int &n) {
    _size = n;
    _iCan = 0;
}

bool candidat::isEnd() const {
    return (_iCan >= _size);
}

int candidat::actual() const {
    if (esEnd()) {
        throw ("No more candidates");
    }
    return _iCan;
}

void candidat::next() {
    if (esFi()) {
        throw ("No more candidates");
    }
    _iCan++;
}

标签： c++algorithmbacktracking

解决方案

我找到了一个可能的解决方案，但它根本不符合要求。

在类求解器中，我创建了一个属性来保存前候选，初始化为 -1。

候选类的构造函数是这样变化的：

candidat::candidat(const int &n, const int &ant) {
    _size = n;
    _iCan = ant + 1;
}

在 solution.h 现在有一个布尔数组来保存可以成为解决方案一部分的候选者。_lvl 被淘汰。

在solver.cpp 中，回溯发生了一些变化，但不应更改。

bool solver::solve(const solution &initial) {
    _found = false;
    _ant = -1;
    _sol = initial;
    findASolution();
    return (_found);
}


void solver::findASolution() {
    **candidat iCan = _sol.inicializateCandidats(_ant);**
    while ((not iCan.isEnd()) and (!_found))
    {
        if (_sol.acceptable(iCan)) {
            _sol.anotate(iCan);
            if(not _sol.complet()) {
                **_ant = iCan.actual();**
                findASolution();
                if (!_found) {
                    _sol.desanotate(iCan);
                }
            }
            else {
                _found = true;
            }
        }
        iCan.next();
    }
}

差异显着。

但这不是最好的解决方案。正确的解决方案应该是使用 _lvl 属性。求解器类不应该知道解决方案的属性。只要它被发现与否。

推荐阅读