我正在尝试实现一个非常基本,非常简单的版本,它可以根据预定的类次列表和预定的人员列表生成学校时间表。
约束和基本设置
为了举例,让我们假设以下问题数据:
5个人,我们称他们为A,B,C,D,E想要分配他们各自的时间表。
每个人都有一个先前选择的类次列表。
每周有5天,让我们假设每天有3个类次,因此,我们有一个3行5列的矩阵。从1开始,代表移动的单元格从上到下从左到右编号。
对于列表:
A = {1,2,3,5,10,11}
B = {6,7,1,3,8,15}
C = {2,6,8,9,12,13}
D = {3,4,5,6,7,8}
E = {6,8,10,11,13,14}
归因于所有类次之后,时间表将是:
A-5,10,11
B-1,7,15
C-2,6,12
D-3,4,9
E-8,13,14
我如何将这个概念推广到现实世界中,比如说20个人40个类次,每个人从8个类次中选择2个。
我的代码如下:
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
#define OPT_DEGREE 300
#define DEBUG 0
#define vpbvi vector<pair<bool,vector<ULL> > >
#define ULL unsigned long long
static string dict[20];
void showV(vector<ULL> & v)
{
for(int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
inline bool do_vectors_intersect(vector<ULL> v1, vector<ULL> v2)
{
unsigned long long int target_sz = v1.size()+v2.size();
set<ULL> s;
for(int i = 0; i < v1.size(); i++)
s.insert(v1[i]);
for(int j = 0; j < v2.size(); j++)
s.insert(v2[j]);
return !(static_cast<ULL>(s.size()) == target_sz); //True se ha intersecçao False c.c.
}
void generateAllPossibleShifts(vector<vector<ULL> > & auxiliar, vector<ULL> & _shifts, int N, int K)
{
string bitmask(K, 1); // K leading 1's
bitmask.resize(N, 0); // N-K trailing 0's
// print integers and permute bitmask
do {
vector<ULL> aux;
for (int i = 0; i < N; ++i) // [0..N-1] integers
{
if (bitmask[i])
{
aux.push_back(_shifts[i]);
if(DEBUG){
cout << " " << _shifts[i];}
}
}
if(DEBUG){
cout << endl << aux.size() << " Done. Create Pair and add to scheudle." << endl;}
pair<bool,vector<ULL> > pbvi = make_pair(true,aux);
for(int i = 0; i < aux.size();i++)
if(DEBUG){
cout << "aux[" <<i<<"] = " << pbvi.second[i] << endl;}
auxiliar.push_back(aux);
// fullVec.push_back(pbvi);
aux.resize(0); //vector is cleared here
if(DEBUG){
cout << "Clear vec" << endl;
cout << pbvi.second.size() << " Done" << endl;
cout << endl;}
} while ( prev_permutation(bitmask.begin(), bitmask.end()));
}
vector<ULL> SumVecs(vector<ULL> & a, vector<ULL> & b)
{
vector<ULL> newVec;
for(int i = 0; i < a.size(); i++)
newVec.push_back(a[i]);
for(int i = 0; i < b.size(); i++)
newVec.push_back(b[i]);
return newVec;
}
void AppendToFirst(vector<ULL> & fst, vector<ULL> & snd, int ind)
{
for(int k = 0; k < snd.size(); k++)
fst.push_back(snd[k]);
}
void OptimizeBeforeNextPassLeft(vector<vector<ULL> > & bsc, vector<vector<ULL> > & arg2)
{
int opt = 0;
for(int i = 0; i < bsc.size(); i++)
{
for(int j = 0; j < arg2.size(); j++)
{
if(do_vectors_intersect(bsc[i],arg2[j])==true){
arg2.erase(remove(arg2.begin(), arg2.end(), arg2[j]), arg2.end());
}
}
}
}
void OptimizeBeforeNextPassRight(vector<vector<ULL> > & bsc, vector<vector<ULL> > & arg2)
{
int opt = 0;
for(int i = bsc.size()-1; i >= 0 ; i--)
{
for(int j = 0; j < arg2.size(); j++)
{
if(do_vectors_intersect(bsc[i],arg2[j])==true){
bsc.erase(bsc.begin()+i);
}
}
}
}
void HardOptimize(vector<vector<ULL> > & bsc, vector<vector<ULL> > & arg2)
{
int opt = 0;
for(int i = bsc.size()-1; i >= 0 ; i--)
{
for(int j = 1; j < arg2.size(); j+=2)
{
if(do_vectors_intersect(bsc[i],arg2[j])==true){
bsc.erase(bsc.begin()+i);
}
}
}
}
//Recursive Function that filters bad attempts and uses "basic" look-ahead technique to narrow search space
//while building an iterative solution. Can still be optimized.
void ExpandSearchSpace(vector<vector<vector<ULL> > > & v, vector<vector<ULL> > & buildSol, int guesslvl, vector<vector<ULL> > & placeholder)
{
if(guesslvl==4) //Num de pessoas-1
{
// cout << "inside ret " << endl << buildSol.size();
placeholder = buildSol;
return;
}
else
{
vector<vector<ULL> > BuildSolCp;
const int ssz = buildSol.size();
for(int i = 0; i < ssz;i++)
{
vector<ULL> arg1 = buildSol[i];
const int ssz2 = v[guesslvl+1].size();
//cout << "arg1.sz() = " << arg1.size() << endl;
for(int j = 0; j < ssz2;j++)
{
if(do_vectors_intersect(buildSol[i], v[guesslvl+1][j])==false){
// cout << "Iter " << guesslvl << " " << buildSol[i].size() << " ";
vector<ULL> arg2 = v[guesslvl+1][j];
// cout << "arg2 " << arg1.size() << " --- ";
vector<ULL> auxi = SumVecs(arg1,arg2);
// cout << "OLFOFKODSJFDSIHFDSFDS" << endl;
BuildSolCp.push_back(auxi);
// cout << "PUSHDED SDUSHFUDSHF"<<endl;
}
}
}
guesslvl++;
if(BuildSolCp.size()> 1000){
cout << "WE neeed optimize Jon" << endl;
for(int i = 0; i < BuildSolCp.size();i++)
showV(BuildSolCp[i]);
vector<vector<ULL> > s= v[guesslvl+1];
//vector<vector<ULL> > s3= v[guesslvl+4];
// vector<vector<ULL> > s4= v[guesslvl+5];
// OptimizeBeforeNextPassLeft(BuildSolCp, s);
OptimizeBeforeNextPassLeft(buildSol,v[guesslvl+2]);
// OptimizeBeforeNextPassRight(BuildSolCp, s);}
// OptimizeFromBothSidesAtOnce(BuildSolCp, v[guesslvl+1][j]);
}
cout << BuildSolCp.size() << " " << guesslvl << endl;
ExpandSearchSpace(v,BuildSolCp, guesslvl, placeholder);
}
// cout << "end" << endl;
}
void ShowPrettyScheudle(vector<vector<ULL> > sol)
{
vector<int> scheudle(15);
for(int j = 0; j <= 10; j+=5){
for(int i = j; i < j+5; i++)
{
cout << sol[0][i] << "\t | ";
}
cout << endl;}
}
int main()
{
static vector<vector<ULL> > WorkerVec1,WorkerVec2,WorkerVec3,WorkerVec4, WorkerVec5;
static vector<vector<ULL> > WorkerVec6,WorkerVec7,WorkerVec8,WorkerVec9, WorkerVec10;
static vector<vector<ULL> > WorkerVec11,WorkerVec12,WorkerVec13,WorkerVec14, WorkerVec15;
static vector<vector<ULL> > WorkerVec16,WorkerVec17,WorkerVec18,WorkerVec19, WorkerVec20;
vector<vector<ULL> > sol;
static vector<vector<vector<ULL>>> v;
vector<ULL> v1{5,10,11,3,1,2}, v2{1,7,3,15,6,8} ,v3{2,6,12,8,13,9}, v4{3,4,5,6,7,8},v5{6,8,10,11,13,14};
generateAllPossibleShifts(WorkerVec1, v1,6,3);
generateAllPossibleShifts(WorkerVec2, v2,6,3);
generateAllPossibleShifts(WorkerVec3, v3,6,3);
generateAllPossibleShifts(WorkerVec4, v4,6,3);
generateAllPossibleShifts(WorkerVec5, v5,6,3);
v.insert(v.end(), {WorkerVec1,WorkerVec2, WorkerVec3,WorkerVec4, WorkerVec5} );
cout << "SIZE OF v[0] in main is " << v[0].size() << endl; //20
for(int i = 0; i < v[0].size(); i++)
{
sol.push_back(v[0][i]);
}
cout << sol.size() << endl; //20
vector<vector<ULL> > plcholder;
cout << "OMG " << plcholder.size()<<endl;
ExpandSearchSpace(v,sol,0,plcholder);
cout << sol.size() << endl;
for(int i = plcholder.size()-1; i >= 0; i--){
cout << plcholder[i].size() << endl;
if(plcholder[i].size()==15){
cout << "FUCK YEA ";showV(plcholder[i]);
cout << endl << endl;
vector<vector<ULL> > vect{plcholder[i]};
ShowPrettyScheudle(vect);
break;}
}
cout << endl;
// cout << endl << Ans[0].size() << " " << Ans[1].size() << " " << Ans[2].size() << " " << Ans[3].size();
return 0;
}
我知道代码很乱,但是其本质很简单:
我基本上是蛮力的,每次通过时,我都会“累积” 3个可能的类次,然后将它们与下一组可能的类次进行比较,直到我只选择了可能的类次到达终点为止。
我试图用一个简单的DP公式甚至是图形来思考,但是,我完全陷入了困境……也许以个人的变化而不是“变化的块”来思考更好,但是,现在,我米茫然。
我已经做了两天了,这让我很紧张
最佳答案
假设有n个人,有m个类次,并且您想为每个人分配s个(必须是s maximum matching的问题。匹配是一组边,因此在一个以上的边中不使用顶点。最大匹配是最大可能大小的匹配。构造图形:
由于A中的2个顶点之间或B中的2个顶点之间没有边,因此生成的图是二分图。您可以使用Hopcroft-Karp算法在O(sqrt(| V |)| E |)时间中找到最大匹配项在第一个链接中;如果存在的话,这将为您提供最佳的解决方案(为每个人分配类次)。 | V | = sn + m,并且| E | = O(snm),因为在最坏的情况下,每个人都有可能列出每个类次,因此总时间复杂度将为O(sqrt(sn + m)snm)。
Ari解决方案的反例
Ari Hietanen's solution是一种很好的启发式方法,但是即使存在解决方案,它也可能无法找到解决方案,如以下示例问题实例所示。
假设我们有8个人A,B,...,H和8个类次1、2,...,8,我们想为每个人分配一个类次,可能的类次矩阵如下所示:
12345678
A XXXXX...
B XXXX....
C XXXX....
D XXXX....
E XXXX....
F ....XXXX
G .....XXX
H .....XXX
X表示该行中的人可以进行该列的平移。
Ari的算法将首先选择类次(第5列),因为只有2个人(A和F),此类次可以比所有其他类次(至少可以由3个人使用)更少的人使用。由于此时A和F均未分配任何类次,因此尚不确定是选择A还是F将5分配给类次,因此很可能会选择F-当然,如果它通过选择拥有最少的可用类次,它将这样做(因为F有4个可能的类次,而A有5个)。但是,一旦做出选择,就无法解决问题,因为这意味着需要以某种方式将4个类次1、2、3和4分配给A,B,C,D和E这5个人,这是不可能的。要查看确实存在解决方案,假设我们将类次5分配给A:现在,我们只需要将4个类次1、2、3和4分配给4个人B,C,D和E,以及3个类次6 ,7和8跨越三个人F,G和H,这很容易做到。