用分支定界(branch and bound)法解装箱问题

装箱问题

[ 问题描述 ]

有一个箱子容量为 v( 正整数, 0≤v≤20000) ,同时有 n 个物品 (0≤n≤30) ,每个物品有一个体积 ( 正整数 ) 。要求从 n 个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

[ 样例 ]

输入:

10 一个整数,表示箱子容量

3 一个整数,表示有 n 个物品

4 接下来 n 行,分别表示这 n 个物品的各自体积。

8

5

输出:

1 一个整数,表示箱子剩余空间。

 
《用分支定界(branch and bound)法解装箱问题》
#include 
<
iostream
>

《用分支定界(branch and bound)法解装箱问题》#include 

<
list
>

《用分支定界(branch and bound)法解装箱问题》
《用分支定界(branch and bound)法解装箱问题》

using
 
namespace
 std;
《用分支定界(branch and bound)法解装箱问题》

#define
 MAX 3

《用分支定界(branch and bound)法解装箱问题》
《用分支定界(branch and bound)法解装箱问题》

const
 
int
 CAP
=
10
;
//
最大容量

《用分支定界(branch and bound)法解装箱问题》《用分支定界(branch and bound)法解装箱问题》

const
 
int
 box[MAX]
=

{4,8,5}
;
//
三个箱子

《用分支定界(branch and bound)法解装箱问题》

int
 main()
《用分支定界(branch and bound)法解装箱问题》《用分支定界(branch and bound)法解装箱问题》


{
《用分支定界(branch and bound)法解装箱问题》    
int temp=0,level=-1,best=0;
《用分支定界(branch and bound)法解装箱问题》    
int curVal=0,parentVal=0,expectVal=0;
《用分支定界(branch and bound)法解装箱问题》    list
<int> queue;
《用分支定界(branch and bound)法解装箱问题》    queue.push_back(
1);//-1表示一层
《用分支定界(branch and bound)法解装箱问题》
    queue.push_back(parentVal);    
《用分支定界(branch and bound)法解装箱问题》    
do
《用分支定界(branch and bound)法解装箱问题》《用分支定界(branch and bound)法解装箱问题》    
{
《用分支定界(branch and bound)法解装箱问题》        parentVal
=queue.front();
《用分支定界(branch and bound)法解装箱问题》        queue.pop_front();
《用分支定界(branch and bound)法解装箱问题》        
if(parentVal!=-1)
《用分支定界(branch and bound)法解装箱问题》《用分支定界(branch and bound)法解装箱问题》        
{
《用分支定界(branch and bound)法解装箱问题》            
//left child
《用分支定界(branch and bound)法解装箱问题》
            curVal=parentVal+box[level];
《用分支定界(branch and bound)法解装箱问题》            
if(curVal>best&&curVal<=CAP)
《用分支定界(branch and bound)法解装箱问题》《用分支定界(branch and bound)法解装箱问题》            
{
《用分支定界(branch and bound)法解装箱问题》                best
=curVal;
《用分支定界(branch and bound)法解装箱问题》                
//最后一层节点没必要加入队列
《用分支定界(branch and bound)法解装箱问题》
                if(level<MAX1)
《用分支定界(branch and bound)法解装箱问题》                    queue.push_back(curVal);
《用分支定界(branch and bound)法解装箱问题》            }

《用分支定界(branch and bound)法解装箱问题》            
《用分支定界(branch and bound)法解装箱问题》            
//right child
《用分支定界(branch and bound)法解装箱问题》
            curVal=parentVal;
《用分支定界(branch and bound)法解装箱问题》            
for(int i=level+1;i<MAX;i++)
《用分支定界(branch and bound)法解装箱问题》                temp
+=box[i];
《用分支定界(branch and bound)法解装箱问题》            expectVal
=curVal+temp;
《用分支定界(branch and bound)法解装箱问题》            
//预计最大值若大于目前最佳值,则加入队列;否则不加入,即剪枝
《用分支定界(branch and bound)法解装箱问题》
            if(expectVal>best&&level<MAX1)
《用分支定界(branch and bound)法解装箱问题》                queue.push_back(curVal);
《用分支定界(branch and bound)法解装箱问题》
《用分支定界(branch and bound)法解装箱问题》《用分支定界(branch and bound)法解装箱问题》        }
else{
《用分支定界(branch and bound)法解装箱问题》            
if(level<MAX1)
《用分支定界(branch and bound)法解装箱问题》                queue.push_back(
1);
《用分支定界(branch and bound)法解装箱问题》            level
++;
《用分支定界(branch and bound)法解装箱问题》        }

《用分支定界(branch and bound)法解装箱问题》
《用分支定界(branch and bound)法解装箱问题》    }
while(level!=MAX&&queue.empty()!=true);
《用分支定界(branch and bound)法解装箱问题》《用分支定界(branch and bound)法解装箱问题》    
/**//*while(queue.empty()!=true)
《用分支定界(branch and bound)法解装箱问题》    {
《用分支定界(branch and bound)法解装箱问题》        cout<<queue.front()<<endl;
《用分支定界(branch and bound)法解装箱问题》        queue.pop_front();
《用分支定界(branch and bound)法解装箱问题》    }
*/

《用分支定界(branch and bound)法解装箱问题》    cout
<<best<<endl;
《用分支定界(branch and bound)法解装箱问题》    
return 0;
《用分支定界(branch and bound)法解装箱问题》}

 

最后输出结果为9

    原文作者:分支限界法
    原文地址: https://blog.csdn.net/zouxinfox/article/details/1933098
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞