最优装载题目.docVIP

最优装载问题 最优装载问题 问题描述 有n个集装箱要装上1艘载重量分别为c的轮船，其中第i个集装箱的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船，并找出一种装载方案 输入 输入有若干组测试数据(不超过20组)。 每组测试数据有2行： 第1行上是集装箱个数n和船的载重量c，（n1000，c65535）； 第2行上有n个整数w1、w2、…、wn，整数之间用一个空格分开，这n个整数依次表示这n个集装箱的重量，（0wi 1000，i=1,2,…,n）。 输出 现要求对输入中的每组测试数据，输出3行： 在第1行上输出“Case #”，其中“#”是测试数据的组号（从1开始）。 在第2行上两个整数bestn、leftc其中bestn是船能装的最多的集装箱数，leftc是对应于bestn的船的最大剩余载重量。 在第3行上输出一个0-1字符串x1x2…xn，其中x1x2…xn是对应于bestn的具体装载方案，xi=1表示第i个集装箱装在船上，而xi=0表示第i个集装箱不装在船上。 对应于bestn的装载方案可能不唯一，如重量分别为40、10、40的3个集装箱，若船的载重量是50，那么只能装2个集装箱上船，因此有装载方案110和011两种。为使输出结果唯一，我们约定长为n的0-1字符串以字典序最大的那个为符合要求的装载方案，此例中应为110。 输入样例 3 50 40 10 40 5 37 10 30 24 35 40 输出样例 Case 1 2 0 110 Case 2 2 3 10100 #include iostream.h //templateclass int class MaxHeap; //templateclass int class HeapNode; class bbnode{ friend void AddLiveNode(MaxHeap,bbnode*,int,int,int); friend int MaxLoading(int*,int,int ,int *); //friend class adjacencygraph; private: bbnode *parent; // 指向父节点的指针 int Lchild; //左儿子节点标志 }; /////////////////////////////////////////////////////////////////////// //templateclass int class HeapNode{ friend void AddLiveNode(MaxHeap,bbnode*,int,int,int); friend int MaxLoading(int*,int,int,int *); public: operator int() const { return uweight;} // private: bbnode *ptr; //指向活节点在子集树中相应节点的指针 int uweight; // 活节点的优先级－－上界 int level; // 活节点在子集树中所处的层序号 }; //template class int class MaxHeap{ friend void AddLiveNode(MaxHeap,bbnode *,int,int,int ); friend i