资源简介
世界名画陈列馆问题的分支限界法解决
代码片段和文件信息
#include
#include
using namespace std;
class Monitor{
int mn;//矩阵的大小
char **Matrix;//矩阵
int *Place;//监控所放置的位置
public:
Monitor(){}
Monitor(int mint n){
int ijroomxy;
this->m = m;
this->n = n;
Matrix = new char *[m];
for(i = 0; i < m; i++)
Matrix[i] = new char [n];
room = m * n;
Place = new int [room];
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
Matrix[i][j] = 0;
i = room / 5;//min是在此矩阵内所需要的最少监控数量
if(room % 5)
i++;//剪枝策略1
for(; i < room; i++){
for(j = 0; j < i; Place[j++] = 1)
SetMonitor(-4j);//-4表示没有监控需要拆除
while(j < room)
Place[j++] = 0;
if(Prem_Modify(i - 1room))
break;
for(x = 0; x < m; x++)//将房间清零
for(y = 0; y < n; y++)
Matrix[x][y] = 0;
}
for(i = 0; i < room; i++){//输出矩阵
if(i != 0 && i % n == 0)
cout< cout< }
cout< for(i = 0; i < m; i++){
for(j = 0; j < n; j++)
cout<<(int)(Matrix[i][j])<<‘ ‘;
cout< }
}
bool Prem_Modify(int layerint room){//layer当前需要移动的监控编号room可移动的上线
if(layer >= 0){
for(int i = layer; i < room; i++){
if(CutBranch(iroomlayer)){
Place[layer] = 0;Place[i] = 1;
if(SetMonitor(layeri))return 1;//0010100000010100
if(Prem_Modify(layer - 1i))return 1;
SetMonitor(ilayer);
Place[i] = 0;Place[layer] = 1;
}
}
return 0;
}
return 0;
}
bool CutBranch(int Range_LTint Range_RDint Surplus){//剪枝
int LTXLTYRDXRDY;//LT左上RD右下
int ij;
LTX = Ra
评论
共有 条评论