我需要排序向量的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)
错误代码示例:
#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
}
发布于 2022-05-27 23:29:20
要找到最好的解决方案,你必须尝试所有的组合。
对彻底搜索的优化:
charge >= avg
,那么它只会使事情变得更糟。throw Perfect()
当所有的回收箱都有平均收费时,不能改进它。--当错误超过最佳错误时,
未使用的优化:
如果一个垃圾桶跳过了一个电荷charge + c1 > avg
.,那么它应该只返回到下一个
c1
按降序排列费用可能是有意义的,这样每个垃圾箱都会迅速装满,而且可能会幸运地早早得到一个完美的适合。我没费什么劲。对于给定的输入,它首先消耗了所有最小的费用,然后在搜索树中越低,选项就越少。最坏的情况下,你可能需要测试每一个组合,而最后一个是最好的解决方案。所以我不确定排序是否在改善搜索时间。
#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;
}
}
https://stackoverflow.com/questions/72410164
复制相似问题