问题描述给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“()”表示。
如果U∈V，且对任意两个顶点u，v∈U有(u,v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。
G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。
G的最大团是指G中所含顶点数最多的团。
如果U∈V且对任意u，v∈U有(u,v)不属于E，则称U是G的空子图。
G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。
G的最大独立集是G中所含顶点数最多的独立集。
对于任一无向图G=(V,E)，其补图G'=(V',E')定义为：V'=V，且(u,v)∈E'当且仅当(u,v)∈E。
如果U是G的完全子图，则它也是G'的空子图，反之亦然。
因此，G的团与G'的独立集之间存在一一对应的关系。
特殊地，U是G的最大团当且仅当U是G'的最大独立集。
例：如图所示，给定无向图G={V,E}，其中V={1,2,3,4,5}，E={(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)}。
根据最大团(MCP)定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。
{1,2,5}是G的一个最大团。
{1,4,5}和{2,3,5}也是G的最大团。
右侧图是无向图G的补图G'。
根据最大独立集定义，{2,4}是G 的一个空子图，同时也是G的一个最大独立集。
虽然{1,2}也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图{1,2,5}中。
{1,2,5}是G'的最大独立集。
{1,4,5}和{2,3,5}也是G'的最大独立集。
算法设计最大团问题的解空间树也是一棵子集树。
算法分析与设计分支限界法分支限界法是一种常用的优化算法，它通过剪枝和分支的方式在空间中找到最优解。
在算法设计与分析中，分支限界法在求解组合优化问题和图论问题中有广泛应用。
分支限界法的基本思想是将问题划分为一个个子问题，并对每个子问题进行求解，同时通过剪枝操作减少空间。
算法从一个初始状态开始，通过扩展子节点来生成树。
在每个节点上，先判断该节点是否需要剪枝操作。
如果需要剪枝，则舍弃该节点及其子节点；如果不需要剪枝，则继续扩展该节点为新的可能解。
通过不断扩展和剪枝操作，最终找到最优解。
分支限界法的核心是选择一个合适的策略来确定节点的扩展顺序。
常用的策略包括优先级队列、最小堆、最大堆等。
这些策略可以根据问题的性质和特点来选择，以保证效率。
同时，剪枝操作也是分支限界法中关键的一环。
剪枝操作有多种方式，如上界和下界剪枝、可行剪枝、标杆剪枝等。
通过剪枝操作，可以减少空间，提高算法的效率。
分支限界法的时间复杂度通常是指数级别的，因为每个节点需要根据策略进行扩展，并进行剪枝操作。
然而，通过合理选择策略和剪枝操作，可以显著减少空间，降低时间复杂度。
此外，分支限界法还可以通过并行计算等技术进一步提高效率。
分支限界法在求解组合优化问题中有广泛应用。
组合优化问题是在有限的资源条件下，通过组合和选择来达到最优解的问题。
例如，旅行商问题、背包问题等都是经典的组合优化问题，而分支限界法可以在有限的时间内找到最优解。
在图论问题中，分支限界法也有重要的应用。
例如，最短路径问题、图着色问题等都可以通过分支限界法求解。
总之，分支限界法是一种基于和剪枝的优化算法，通过合理选择策略和剪枝操作，在有限的时间内找到最优解。
该算法在组合优化问题和图论问题中有广泛应用，可以有效提高问题求解的效率。
在实际应用中，可以根据问题性质和特点选择合适的策略和剪枝操作，以达到最佳的求解效果。
分支限界法一般原理转化为一艘船的最优化问题后，问题的解空间为一个子集树。
也就是算法要考虑所有物品取、舍情况的组合，n个物品的取舍组合共有2的n次方个分支。
1> 和回溯算法的思想一样，用FIFO分支搜索所有的分支，并记录已搜索分支的最优解，搜索完子集树也就找出了问题的解。
2> 要想求出最优解，必须搜索到叶结点，所以要记录数的层次。
当层次为n+1时，搜索完全部叶结点，算法结束。
3> 分支搜索过程中活结点的"层"是需要标识的，否则入队后无法识别结点所在的层。
每处理完一层让"-1"入队，以此来标识"层"，并用变量i来记录当前层。
4> 每个活结点要记录当前船的装载量。
问题描述假设有n个货物。
分别为w={...}。
船的最大载重量为C.选择一种最优的载模式，使其装载的重量最大，假设:n=6. w={10,20,50,50,100,122} c=180。
那么这个船实际上可装载的最大重量为多少呢？源码#include<iostream>using namespace std;/****************************************************************************/ struct bbnode{bbnode *parent;bool LChild;};struct HeapNode{bbnode *ptr;int uweight;int level;};/****************************************************************************//****************************************************************************/ typedef HeapNode ElemType;#define MaxData 32767typedef struct Heap{int capacity;int size;HeapNode *Elem;}Heap,*HeapQueue;HeapQueue init(int maxElem){HeapQueue H=new Heap;H->capacity=maxElem;H->size=0;H->Elem=new HeapNode[maxElem+1];H->Elem[0].uweight=MaxData;return H;}void InsertMax(ElemType x,HeapQueue H){int i;for(i=++H->size;H->Elem[i/2].uweight<x.uweight;i/=2)H->Elem[i]=H->Elem[i/2];//此时i还没有进行i/2操作H->Elem[i]=x;}ElemType DeleteMax(HeapQueue H){int i,child;ElemType MaxElem,LastElem; //存储最大元素和最后一个元素。
