首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >电池组装用锂电池分选机

电池组装用锂电池分选机
EN

Stack Overflow用户
提问于 2022-05-27 19:21:40
回答 1查看 54关注 0票数 0

我需要排序向量的N个子向量(或分段原向量在块上)的k长度和尽可能多的相等的“块”。

我知道像repackr.com这样的网站,但我需要这段代码来做我的课程,不幸的是,我不能改变主题。你可以说我是个懒惰的人,但是我已经做了两个星期的算法了,而且我还没有达到预期的结果。我还没有在堆栈溢出或互联网上发现类似的算法实现。

输入示例:1 2 3 4 5 6 7 8 9

示例不正确的输出:

9 1 5(共计:15差:0)

8 2 6(共计:16差:1)

7 3 4(总计:14差:-1)

示例正确输出:

9 1 5(共计:15差:0)

7 2 6(共计:15差:0)

8 3 4(共计:15差:0)

错误代码示例:

代码语言:javascript
运行
复制
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

class cells {
    vector <double> cellsCap; //List of cell capacities
    vector <double> blockSum; //Block capacity
    vector <double> blockDiff; //The difference is relative to the average capacity
    int S, P; //S - In Series P - In Parallel
public:
    void Cellsfinput(const string& fname) { //File input
        ifstream fin;
        fin.open(fname);
        double intmp;

        while (fin >> intmp) {
            cellsCap.push_back(intmp);
        }
        fin.close();
    }

    void SPinput(const int& Sinp, const int& Pinp) { //S, P input for Cellsfinput.
        S = Sinp;
        P = Pinp;
        for (int i = 0; i < S; ++i) blockSum.push_back(0);
    }

    void Cellsconsinput(vector <double> cellsCapinp, const int& Sinp, const int& Pinp) { //Input from arguments
        S = Sinp;
        P = Pinp;

        for (int i = 0; i < S * P; ++i) cellsCap.push_back(cellsCapinp[i]);
        for (int i = 0; i < S; ++i) blockSum.push_back(0);
    }

    void Cellsfoutput(const string& fname) { //File output

        ofstream fout;
        fout.open(fname);

        double tmp;

        for (int i = 0; i < S; ++i) {
            fout << "Block№" << i + 1 << " ";
            tmp = 0;
            for (int k = i; k < cellsCap.size(); k += S) {
                tmp += cellsCap[k];
                fout << cellsCap[k] << ' ';

            }
            fout << "Total:" << tmp << " Diff:" << blockDiff[i] << endl;
        }

        fout.close();
    }

    void Cellsconsoutput() { //Console output
        double tmp;
        for (int i = 0; i < S; ++i) {
            cout << "Block№№" << i + 1 << " ";
            tmp = 0;
            for (int k = i; k < cellsCap.size(); k += S) {
                tmp += cellsCap[k];
                cout << cellsCap[k] << ' ';

            }
            cout << "Total:" << tmp << " Diff:" << blockDiff[i] << endl;
        }
    } 

    void sortcells() {
        sort(cellsCap.rbegin(), cellsCap.rend());

    vector <double> sortedVec; //Assembled, sorted (at the end) vector
    double midCap; //Average capacity of blocks in an assembly
        long double midTmp = 0;

        for (int i = 0; i < S * P; ++i) midTmp += cellsCap[i]; //midCap calculation
        midCap = midTmp / S;

        for (int i = P; i > 0; --i) { //Iterating through blocks
            for (int k = 0; k < S; ++k) { //Iterating through the elements in the block
                if (i == P) { //Initial filling with maximum elements (controversial decision)
                    sortedVec.push_back(cellsCap[0]);
                    blockSum[k] += cellsCap[0];
                    cellsCap.erase(cellsCap.begin());
                    continue;
                }
                for (int j = cellsCap.size() - 1; j >= 0; --j) { //Iterating over elements for parallels
                    if (j == 0) { //If there is no suitable cell, it takes the largest
                        sortedVec.push_back(cellsCap[0]);
                        blockSum[k] += cellsCap[0];
                        cellsCap.erase(cellsCap.begin());
                        break;
                    }
                    if (blockSum[k] + cellsCap[j] >= midCap / i) { //The main logic of selection takes the first element in the block that +- coincides with the average value for this "vertical".
                        sortedVec.push_back(cellsCap[j]);
                        blockSum[k] += cellsCap[j];
                        cellsCap.erase(cellsCap.begin() + j);
                        break;
                    }
                }
            }
        }
        cellsCap = sortedVec;

        for (int i = 0; i < S; ++i) blockDiff.push_back(blockSum[i] - midCap);

        /*int tmp, minDiffa, minDiffb; //Bad code
        for (int i = 0; i < S; ++i) {
            for (int k = i; k < cellsCap.size(); k += S) {
                for (int j = S - 1; j > i; --j) {
                    for (int t = j; t < cellsCap.size(); t += S) {
                        if (abs(blockDiff[i] + (cellsCap[k] - cellsCap[t])) < abs(blockDiff[i]) && abs(blockDiff[j] + (cellsCap[t] - cellsCap[j])) < abs(blockDiff[j])) {
                            cout << endl << "k:" << k << " t:" << t << " K-T: " << cellsCap[k] - cellsCap[t] << " K:" << cellsCap[k] << " T:" << cellsCap[t] << endl;
                            
                        }
                    }
                }
            }
        } */
} 
};

int main() {
    cells block;
    block.Cellsfinput("123.txt "); //Input
    block.SPinput(3, 3); //Input S (serial connection) and P (parallel connection)
    block.sortcells(); //Sorting
    block.Cellsfoutput("1234.txt "); //Output
} 
EN

回答 1

Stack Overflow用户

发布于 2022-05-27 23:29:20

要找到最好的解决方案,你必须尝试所有的组合。

对彻底搜索的优化:

  1. 最大的电荷总是在0的垃圾桶里,其他的只是垃圾箱的排列。

  1. ,如果一个垃圾桶已经有了charge >= avg,那么它只会使事情变得更糟。

  1. 最后一个垃圾箱总是得到所有未使用的费用。--

  1. throw Perfect()当所有的回收箱都有平均收费时,不能改进它。--

当错误超过最佳错误时,

  1. 中止递归。

未使用的优化:

如果一个垃圾桶跳过了一个电荷charge + c1 > avg.,那么它应该只返回到下一个

  1. 如果是c1

按降序排列费用可能是有意义的,这样每个垃圾箱都会迅速装满,而且可能会幸运地早早得到一个完美的适合。我没费什么劲。对于给定的输入,它首先消耗了所有最小的费用,然后在搜索树中越低,选项就越少。最坏的情况下,你可能需要测试每一个组合,而最后一个是最好的解决方案。所以我不确定排序是否在改善搜索时间。

代码语言:javascript
运行
复制
#include <iostream>
#include <vector>
#include <numeric>

class Perfect { };

void dosolve(const std::vector<double> &charges,
             std::vector<int> &bins,
             int num_bins,
             double avg,
             int bin,
             size_t index,
             double charge,
             double error,
             double &best_error,
             std::vector<int> &best) {
    if (bin + 1 == num_bins) {
        // last bin takes all remaining cells
        for (size_t i = 0; i < charges.size(); ++i) {
            if (bins.at(i) == -1) {
                charge += charges.at(i);
            }
        }
        error += abs(avg - charge);
        if (error < best_error) {
            best_error = error;
            best = bins;
            // take charges for real
            for (size_t i = 0; i < charges.size(); ++i) {
                if (best.at(i) == -1) {
                    best.at(i) = bin;
                }
            }
            if (error == 0) throw Perfect();
        }
        return;
    }
    if ((charge >= avg) || (index >= charges.size())) {
        // bin has no more charges to take, next bin
        error += std::abs(avg - charge);
        if (error < best_error) dosolve(charges, bins, num_bins, avg, bin + 1, 0, 0, error, best_error, best);
    } else {
        if (bins.at(index) == -1) {
            // take charge
            bins.at(index) = bin;
            dosolve(charges, bins, num_bins, avg, bin, index + 1, charge + charges.at(index), error, best_error, best);
            bins.at(index) = -1;
        }
        // skip charge
        dosolve(charges, bins, num_bins, avg, bin, index + 1, charge, error, best_error, best);
    }

}

std::vector<int> solve(const std::vector<double> charges, int num_bins) {
    std::vector<int> bins(charges.size(), -1);
    std::vector<int> best;
    const double total = std::accumulate(charges.begin(), charges.end(), 0);
    std::cout << "Solving for " << num_bins << ": avg = " << total / num_bins << std::endl;
    double best_error = total * (num_bins - 1) + 1; // larger than one bin taking all charges
    // largest charge goes into bin 0
    size_t max_index = 0;
    size_t max_charge = charges.at(0);
    for (size_t i = 1; i < charges.size(); ++i) {
        if (charges.at(i) > max_charge) {
            max_index = i;
            max_charge = charges.at(i);
        }
    }
    bins.at(max_index) = 0;
    // search all combinations and catch a perfect solution
    try {
        dosolve(charges, bins, num_bins, total / num_bins, 0, 0, max_charge, 0, best_error, best);
    } catch (Perfect&) { }
    return best;
}

int main() {
    const std::vector<double> charges{1, 2, 3, 4, 5, 6, 7, 8, 9};
    const int NUM_BINS = 3;
    const std::vector<int> bins = solve(charges, NUM_BINS);
    for (int bin = 0; bin < NUM_BINS; ++bin) {
        std::cout << bin << ":";
        double charge = 0;
        for (size_t i = 0; i < charges.size(); ++i) {
            if (bins.at(i) == bin) {
                std::cout << " " << charges.at(i);
                charge += charges.at(i);
            }
        }
        std::cout << " : " << charge << std::endl;
    }
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/72410164

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档