这个月参加了华为编程挑战赛，（初赛赛题：http://codecraft.devcloud.huaweicloud.com/home/detail）。
分配部分的代码主要由我负责，放出来做个备份。
背包法的参考资料：
https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin
https://blog.csdn.net/na_beginning/article/details/62884939
1. distrubute.h
#ifndef Dis_H
#define Dis_H
#include <string>
#include <iostream>
#include "predict.h"
#include <list>
using namespace std;
#define ISCPU true
#define ISMEM false
#define FLAVORNUMMAX 999
#define LOWISTRATE 0.3
#define LOWRATE 0.95
//int f[FLAVORNUMMAX][CPUSUM+1][MEMSUM+1] = { 0 }; // 存放value的数组
//bool g[FLAVORNUMMAX][CPUSUM+1][MEMSUM+1] = { false }; // 存放是否放入背包的数组
class Flavor
{
public:
string flavor;
int CPU;
int Memory;
Flavor(const string FLAVOR){
flavor = FLAVOR;
str2int(type,FLAVOR);
switch (type)
{
case 1:
CPU = 1;
Memory = 1;
break;
case 2:
CPU = 1;
Memory = 2;
break;
case 3:
CPU = 1;
Memory = 4;
break;
case 4:
CPU = 2;
Memory = 2;
break;
case 5:
CPU = 2;
Memory = 4;
break;
case 6:
CPU = 2;
Memory = 8;
break;
case 7:
CPU = 4;
Memory = 4;
break;
case 8:
CPU = 4;
Memory = 8;
break;
case 9:
CPU = 4;
Memory = 16;
break;
case 10:
CPU = 8;
Memory = 8;
break;
case 11:
CPU = 8;
Memory = 16;
break;
case 12:
CPU = 8;
Memory = 32;
break;
case 13:
CPU = 16;
Memory = 16;
break;
case 14:
CPU = 16;
Memory = 32;
break;
case 15:
CPU = 16;
Memory = 64;
break;
default:
cout << "ERROR: ÊäÈëµÄÐéÄâ»úÐͺÅûÓÐÕÒµ½" << endl;
}
}
int type; // 0~15 虚拟机型号
};
class BagItem
{
public:
string flavor;
int CPUWeight;
int memoryWeight;
int value; // 该虚拟机的CPU个数或内存大小
int num; // 有多少种该虚拟机
BagItem(const Flavor FLAVOR, const int NUM, const bool CM1){
flavor = FLAVOR.flavor;
CPUWeight = FLAVOR.CPU * NUM;
memoryWeight = FLAVOR.Memory * NUM;
value = (CM1 == ISCPU) ? CPUWeight : memoryWeight;
num = NUM;
type = FLAVOR.type;
};
int type; // 0~15 虚拟机型号
};
class PhysicalServer
{
public:
list<BagItem> flavorList; // ·物理机上存放的虚拟机列表
int num; // ÎïÀí»ú±êºÅ
PhysicalServer(int NUM)
{
num = NUM;
};
};
list<BagItem> PreTreatmentSingle(const Flavor flavor, const int NUM);
list<BagItem> PreTreatment(list<Flavor> flavorList, int * num);
void InitialFlavorList(list<Flavor> &flavorList);
void GetF(list<BagItem> itemList);
void GetG(list<BagItem> &itemList, list<PhysicalServer> &serverList);
list<PhysicalServer> GetPhysicalServerList(list<BagItem> &itemList, list<PhysicalServer> &serverList);
vector<double> Distribute(list<PhysicalServer> &serverList, int *a,bool CM_in,int CPUSUM_in, int MEMSUM_in);
#endif
2. distrubute.cpp
#include "distribute.h"
#include <iostream>
#include <list>
#include <vector>
#include <exception>
using namespace std;
bool CM;
int CPUSUM; // 物理服务器的cpu总数
int MEMSUM; // 物理服务器的内存总量
//#define LOWISTRATE 0.3
list<BagItem> PreTreatmentSingle(const Flavor flavor, const int NUM )
{
list<BagItem> itemList;
if (NUM <= 0)
{
return itemList;
}
if (NUM == 1)
{
BagItem item(flavor, NUM, CM);
itemList.push_back(item);
return itemList;
}
int n = NUM;
int k = 1;
while (n > 1)
{
BagItem item(flavor, k, CM);
itemList.push_back(item);
k = k * 2;
n = n / 2;
}
BagItem item(flavor, NUM - k + 1, CM);
itemList.push_back(item);
return itemList;
}
// 预处理
list<BagItem> PreTreatment(list<Flavor> flavorList, int * num)
{
list<BagItem> bagItemList;
int j = 0;
list<Flavor>::iterator it;
for(it = flavorList.begin(); it != flavorList.end(); it++) //for each (auto flavor in flavorList)
{
Flavor flavor = *it;
if (num[j] != 0){
for (int i = 0; i < num[j]; i++)
{
BagItem item(flavor, 1, CM);
bagItemList.push_back(item);
}
}
j++;
}
return bagItemList;
}
void InitialFlavorList(list<Flavor> &flavorList)
{
for (int i = 1; i <= 15; i++)
{
Flavor flavor(to_string(i));
flavorList.push_back(flavor);
}
}
int f[FLAVORNUMMAX][100][513] = { 0 };
bool g[FLAVORNUMMAX][100][513] = { false };
list<PhysicalServer> serverList;
void GetF(list<BagItem> itemList)
{
int i = 0;
list<BagItem>::iterator it = itemList.begin();
for (it = itemList.begin(); it != itemList.end();it++)
{
BagItem bagItem = *it;
for (int u = 1; u <= CPUSUM; u++)
{
for (int v = 1; v <= MEMSUM; v++)
{
if ((i > 0) && (u - bagItem.CPUWeight >= 0) && (v - bagItem.memoryWeight >= 0)) // 一般情况
{
if (f[i - 1][u][v] < f[i - 1][u - bagItem.CPUWeight][v - bagItem.memoryWeight] + bagItem.value)
{
f[i][u][v] = f[i - 1][u - bagItem.CPUWeight][v - bagItem.memoryWeight] + bagItem.value;
g[i][u][v] = true;
}
else if (f[i - 1][u][v] == f[i - 1][u - bagItem.CPUWeight][v - bagItem.memoryWeight] + bagItem.value)
{
f[i][u][v] = f[i - 1][u][v];
--it;
g[i][u][v] = bagItem.value>(*it).value ? true : false;
++it;
}
else
{
f[i][u][v] = f[i - 1][u][v];
g[i][u][v] = false;
}
}
else if (i == 0) // 第一行
{
if ((u - bagItem.CPUWeight >= 0) && (v - bagItem.memoryWeight >= 0)) {
f[i][u][v] = bagItem.value;
g[i][u][v] = true;
}
else{
f[i][u][v] = 0;
g[i][u][v] = false;
}
}
else // 重量减了之后超限
{
f[i][u][v] = f[i - 1][u][v];
g[i][u][v] = false;
}
}
}
i++;
}
}
void GetG(list<BagItem> &itemList, list<PhysicalServer> &serverList)
{
int u = CPUSUM ;
int v = MEMSUM ;
int i = itemList.size() - 1;
PhysicalServer physicalServer(serverList.size());
list<BagItem>::iterator it = itemList.end(); // 迭代器初始化为数组最末尾
for (it--; it != itemList.begin(); it--) // 逆序访问物品列表
{
if (g[i][u][v])
{
physicalServer.flavorList.push_back(*it); // 放在该物理机中
u = u - (*it).CPUWeight;
v = v - (*it).memoryWeight;
it = itemList.erase(it); // 删除元素, 指向被删除元素之后的元素
}
i--;
} // 直到it指向itemList.begin，此时i应等于0
if (g[i][u][v]) // 处理itemList.begin这个元素
{
physicalServer.flavorList.push_back(*it); // 放在该物理机中
itemList.erase(it); // 删除元素, 指向被删除元素之后的元素
}
serverList.push_back(physicalServer);
}
list<PhysicalServer> GetPhysicalServerList(list<BagItem> &itemList, list<PhysicalServer> &serverList)
{
while (itemList.size() > 0)
{
GetF(itemList);
GetG(itemList, serverList);
}
return serverList;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
void AddFlavor(list<BagItem> &flavorList, int *a, bool CM_in, int CPUSUM_in, int MEMSUM_in)
{
int cpuu = 0;
int mem = 0;
list<BagItem>::iterator it2;
for (it2 = flavorList.begin(); it2 != flavorList.end(); it2++)
{
cpuu += (*it2).CPUWeight * (*it2).num;
mem += (*it2).memoryWeight * (*it2).num;
}
int cpuLeft = CPUSUM_in-cpuu;
int memLeft = MEMSUM_in-mem;
// int order[10]={ 13, 12, 10, 9, 7, 6, 4, 3 ,1, 0 }; // flavor14,flavor13, 11, 10...... 2, 1
// if(CM_in == ISMEM)
// {
// order[0]=14; // flavor15;
// order[1]=11; // flavor12;
// order[2]=8; // flavor9;
// order[3]=7; // flavor8;
// order[4]=5; // flavor6;
// order[5]=4; // flavor5;
// order[6]=2; // flavor3;
// order[7]=3; // flavor4;
// order[8]=1; // flavor2;
// order[9]=0; // flavor1;
// }
// int order[7]={ 12, 9, 6, 3, 0, 0, 0 }; // flavor14,flavor13, 11, 10...... 2, 1
// if(CM_in == ISMEM)
// {
// order[0]=14; // flavor15;
// order[1]=11; // flavor12;
// order[2]=8; // flavor9;
// order[3]=5; // flavor6;
// order[4]=2; // flavor3;
// order[5]=1; // flavor2;
// order[6]=0; // flavor1;
// }
int order[10]={9, 7, 6, 13, 12, 10, 4, 3 ,1, 0 }; // flavor14,flavor13, 11, 10...... 2, 1
if(CM_in == ISMEM)
{
order[0]=8; // flavor9;
order[1]=7; // flavor8;
order[2]=5; // flavor6;
order[3]=14; // flavor15;
order[4]=11; // flavor12;
order[5]=4; // flavor5;
order[6]=2; // flavor3;
order[7]=3; // flavor4;
order[8]=1; // flavor2;
order[9]=0; // flavor1;
}
for(int i=0;i<10;i++)
{
if(a[order[i]]>=0) // if flavor i need be predicted
{
Flavor f(to_string(order[i]+1));
BagItem flavor(f, 1, CM_in);
while((cpuLeft >= flavor.CPUWeight)&&(memLeft >= flavor.memoryWeight))
{
for (it2 = flavorList.begin(); it2 != flavorList.end(); it2++)
{
if ((*it2).type == flavor.type)
{
(*it2).num++ ;
break;
}
}
if(it2 == flavorList.end())
flavorList.push_back(flavor);
a[order[i]]++;
cpuLeft -= flavor.CPUWeight;
memLeft -= MEMSUM_in-mem;
}
}
}
}
vector<double> mend(list<PhysicalServer> &serverList, int *a,bool CM_in,int CPUSUM_in, int MEMSUM_in)
{
CM = CM_in;
CPUSUM = CPUSUM_in;
MEMSUM = MEMSUM_in;
list<PhysicalServer>::iterator it;
//cout<<"hhhhhh"<<endl;
for(it = serverList.begin(); it != serverList.end(); it++)// each (auto server in serverList)
{
//PhysicalServer server = *it;
//cout << server.num << ":" << endl;
int cpuu = 0;
int mem = 0;
list<BagItem>::iterator it2;
for (it2 = (*it).flavorList.begin(); it2 != (*it).flavorList.end(); it2++)
{
cpuu += (*it2).CPUWeight * (*it2).num;
mem += (*it2).memoryWeight * (*it2).num;
}
double cp = cpuu*1.0 / CPUSUM;
double me = mem*1.0 / MEMSUM;
if ((CM==ISCPU && cp < LOWISTRATE)||(CM==ISMEM && me < LOWISTRATE))
{
for (it2 = (*it).flavorList.begin(); it2 != (*it).flavorList.end(); it2++)
{
a[(*it2).type-1] = a[(*it2).type-1] - (*it2).num;
cout<<(*it2).type<<"::"<<(*it2).num<<endl;
}
it = serverList.erase(it);
}
else if ((CM==ISCPU && cp < LOWRATE)||(CM==ISMEM && me < LOWRATE))
{
AddFlavor( (*it).flavorList, a, CM_in, CPUSUM_in, MEMSUM_in);
}
}
double cpurate = 0;
double memrate = 0;
int m = 0;
for(it = serverList.begin(); it != serverList.end(); it++)// each (auto server in serverList)
{
//PhysicalServer server = *it;
(*it).num = m;
m++;
//cout << server.num << ":" << endl;
int cpuu = 0;
int mem = 0;
list<BagItem>::iterator it2;
for (it2 = (*it).flavorList.begin(); it2 != (*it).flavorList.end(); it2++)
{
cpuu += (*it2).CPUWeight * (*it2).num;
mem += (*it2).memoryWeight * (*it2).num;
}
double cp = cpuu*1.0 / CPUSUM;
double me = mem*1.0 / MEMSUM;
cpurate = cpurate + cp;
memrate = memrate + me;
}
cout << cpurate / m << "\t" << memrate/m << endl;
vector<double> score2;
score2.push_back(cpurate / m);
score2.push_back(memrate / m );
for(int i=0;i<15;i++)
cout<<a[i]<<" ";
cout<<endl;
// if((CM==ISCPU && cpurate / m< LOWRATE )||(CM==ISMEM && memrate / m < LOWRATE))
// for(int i=0;i<15;i++)
// a[i]=10000;
return score2;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
vector<double> Distribute(list<PhysicalServer> &serverList, int *a,bool CM_in,int CPUSUM_in, int MEMSUM_in)
{
for(int i=0; i<FLAVORNUMMAX; i++)
{
for(int k=0; k<100; k++)
{
for(int j=0; j<513; j++)
{
f[i][k][j]=0;
g[i][k][j]=false;
}
}
}
serverList.clear();
CM = CM_in;
CPUSUM = CPUSUM_in;
MEMSUM = MEMSUM_in;
list<Flavor> flavorList;
InitialFlavorList(flavorList);
//int a[15] = { 6, 1, 6, 3, 9, 9, 0, 59, 8, 2, 11, 0, 1, 16, 0 };
list<BagItem> bagItemList = PreTreatment(flavorList, a);
/*for each (auto var in bagItemList)
{
cout << var.flavor << "\t" << var.num << endl;
}*/
// list<PhysicalServer> serverList;
serverList = GetPhysicalServerList(bagItemList, serverList);
double cpurate = 0;
double memrate = 0;
int m = 0;
list<PhysicalServer>::iterator it;
//cout<<"hhhhhh"<<endl;
for(it = serverList.begin(); it != serverList.end(); it++)// each (auto server in serverList)
{
//PhysicalServer server = *it;
m++;
//cout << server.num << ":" << endl;
int n = 0;
int cpuu = 0;
int mem = 0;
list<BagItem>::iterator it2;
for (it2 = (*it).flavorList.begin(); it2 != (*it).flavorList.end(); it2++)
{
list<BagItem>::iterator it20 = it2;
it20++;
while ((it20 != (*it).flavorList.end()) && ((*it20).flavor == (*it2).flavor))//(flavor.flavor == (*it2).flavor)
{
(*it2).num++;
it20 = (*it).flavorList.erase(it20);
}
//cout << (*it2).flavor << "\t" << (*it2).num << endl;
n += (*it2).num;
cpuu += (*it2).CPUWeight * (*it2).num;
mem += (*it2).memoryWeight * (*it2).num;
}
double cp = cpuu*1.0 / CPUSUM;
double me = mem*1.0 / MEMSUM;
cpurate = cpurate + cp;
memrate = memrate + me;
//cout << n << "\t" << cp << "\t" << me << endl;
//cout << endl;
}
cout << cpurate / m << "\t" << memrate/m << endl;
//char c;
//c = getchar();
vector<double> score2 = mend(serverList, a, CM_in, CPUSUM_in, MEMSUM_in);
// vector<double> score2;
// score2.push_back(cpurate / m);
// score2.push_back(memrate / m );
return score2;
}
网友评论