• 大小: 4KB
    文件类型: .cpp
    金币: 1
    下载: 0 次
    发布日期: 2021-05-14
  • 语言: C/C++
  • 标签: 陈列问题  

资源简介

世界名画陈列馆问题的分支限界法解决

资源截图

代码片段和文件信息

#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

评论

共有 条评论

相关资源