435-分支限界算法-集装箱装载问题

清疚 2022-09-05 11:23 190阅读 0赞

## 集装箱装载问题 ##

**有一批共n个集装箱要装上2艘载重量分别为c1,c2的轮船，其中集装箱的重量为wi,且要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。**

思路：  
**我们要尽最大可能把一个轮船塞得越满越好，让c1的轮船最大化装载。然后把剩下的集装箱装上另一个轮船。**

**我们定义**

int w[] = {
         12, 8, 15 };//集装箱的重量
    const int n = sizeof(w) / sizeof(w[0]);//集装箱的数量
    int c = 27;//轮船的容量
    int cw = 0;//已选择物品的重量
    int bestw = 0;//记录最优的装载量

**我们的左孩子表示选择（1），右孩子表示不选择（0），我们先处理左孩子。**

因为是层序遍历，一层一层的遍历，我们先处理第一层：  
每一层是从左向右处理的  
**第一层**（从左向右）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
**处理第二层**（从左向右）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**处理最后一层**（从左向右）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
**我们看出，最优解是这个红色框起来的叶子节点**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
**我们是广度优先遍历，找到最优解。但是不能获取到哪些集装箱进了轮船。**  
**所以我们在扩展孩子节点的时候要记录一下父节点是谁，通过parent找见。还得知道是否选择该节点，所以还要增加个标识判断！！！**

## 分支限界解题代码 ##

#include <iostream>
    #include <queue>
    using namespace std;
    
    
    int w[] = {
         12, 8, 15 };//集装箱的重量
    const int n = sizeof(w) / sizeof(w[0]);//集装箱的数量
    int c = 20;//轮船的容量
    int cw = 0;//已选择物品的重量
    int bestw = 0;//记录最优的装载量
    
    //描述节点类型
    struct Node 
    {
        
    	Node(int w, int l, Node *p, bool left) 
    	{
        
    		weight = w;
    		level = l;
    		parent = p;
    		isleft = left;
    	}
    	int weight;//从根节点到当前节点所选择物品的总重量
    	int level;//当前节点的层数
    	Node *parent;//记录当前节点的父节点
    	bool isleft;//记录当前节点是否被选择，true就是被往左选择
    };
    
    //广度优先遍历子集树的FIFO队列（先进先出队列）
    queue<Node*> que;
    int i = 0;//表示起始的层数，从根节点开始
    Node *bestnode = nullptr;
    int r = 0;//记录未被处理的物品的总重量
    
    //添加活结点到队列当中
    void addLiveNode(int w, int level, Node *parent, bool isleft) 
    {
        
    	Node *node = new Node(w, level, parent, isleft);
    	que.push(node);
    
    	//在最后一层，记录最优值节点
    	if (level == n && w == bestw) 
    	{
        
    		bestnode = node;
    	}
    }
    //节点的上界函数， 返回未被处理的物品的总重量
    int maxBound(int level) 
    {
        
    	int s = 0;
    	for (int j = level + 1; j < n; ++j)//当前level是正在处理的节点 
    	{
        
    		s += w[j];
    	}
    	return s;
    }
    int main()
    {
        
    	Node *node = nullptr; //初始状态，根节点无父节点
    	while (i < n) 
    	{
           //当前节点是第i层 0   开始扩展node节点
    		//处理左孩子，表示选择i节点
    		int wt = cw + w[i];//已选择的物品加上即将选择的物品 
    		if (wt <= c)//选择物品i以后，其总重量不能超过轮船的容量 
    		{
         
    			if (wt > bestw)//更新一下 bestw
    			{
        
    				bestw = wt;
    			}
    
    			//活结点孩子入队列
    			//que.push(Node(cw + w[i], i + 1));
    			addLiveNode(cw+w[i], i+1, node, true);
    		}
    
    		//处理右孩子，表示不选择i节点
    		//que.push(Node(cw, i + 1));
    		r = maxBound(i);//求第i个节点的重量值上界  
    		if (cw + r >= bestw) 
    		{
         //>=这里的=操作不能少，否则无法选择到叶子节点上 c=20
    			addLiveNode(cw, i + 1, node, false);
    		}
    		
    		//处理完i节点后，它成为死节点，然后出队
    		node = que.front();
    		que.pop();
    		//恢复cw和i的值，表示从i节点跳到广度遍历的下一个节点了
    		//因为是层序遍历，所以要恢复一下
    		cw = node->weight; 
    		i = node->level;
    	}
    
    	cout << bestw << endl;
    	int bestx[n] = {
         0 };
    	for (int j = n - 1; j >= 0; --j) 
    	{
        
    		bestx[j] = bestnode->isleft ? 1 : 0;
    		bestnode = bestnode->parent;
    	}
    	for (int v : bestx) 
    	{
        
    		cout << v << " ";
    	}
    	cout << endl;
    
    	return 0;
    }

**运行截图如下**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/2410bb846f0440528cc42109015a89c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/0ce1d0904575410da9510473e4476325.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/efeaaea10e9c46ad94cb362e308cea8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/24f40530d3f24cbbb8792394dfb75dfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/a678534716bf4fe9829421b6f17a16ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/274c1051463841e18d07bb2719df8d62.png