第二届'华为杯'软件设计大赛题目命题组题目1`动态多维度

《第二届'华为杯'软件设计大赛题目命题组题目1`动态多维度》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、“神马都浮云，编程最给力”第二届“华为杯”软件设计大赛题目——命题组题目1、动态多维度装箱算法题目描述：装箱算法是一个著名的NP难解问题，其在工业生产及日常生活中有着广泛的应用场景。设计要求：一、说明1）箱子和物品可以用一个多维向量来表示，简称维度（维度>3）；2）箱子的各个维度的大小初始化之后固定不变；3）物品的各个维度的大小会动态变化；4）判断一个箱子是否能够容下物品的办法是：箱子中所有物品任一维度的和小于箱子相应维度的大小；5）如果箱子容不下箱子里的物品，则需要把某些物品搬到其他容得下这些物品的箱子中

2、；6）物品变大是指物品的某个或多个维度值变大了，变小则相反；二、问题描述假设共有X（X>60）个箱子和Y(Y>3000)个物品，初始状态时Y个物品都在X个箱子中。每隔3秒钟，所有物品的大小都会变化，算法模块检测是否存在某个箱子装不下物品的情况，然后决定如何通过搬物品解决。三、算法目标设计一个动态多维度装箱算法：1）当物品变得比较大时，如果出现箱子容不下物品的情况，需要把这箱子中的物品搬到其他箱子中（可能需要多次搬物品）；2）当物品变得比较小时，尽量把物品放到尽量少的箱子中；规格说明：1）决策时间少于0.2秒

3、作品格式：1）算法设计文档2）算法模块源码3）检验算法性能的测试程序源码和可执行文件评选标准：1）装箱的准确度2）装箱的决策时间3）箱子和物品数量的规模题目2、URL匹配算法研究题目描述：URL匹配是指URL库中高效匹配出与当前给定URL最符合的库中的URL条目。设计要求：构建URL库规则，需要包含如下的一些URL样式：不含通配符匹配1.在规则中未出现通配符的场景，则采用最大匹配原则。例：配置规则：http://www.huawei.comhttp://www.huawei.com能匹配上http://ww

4、w.huawei.com/huawei能匹配上http://www.huawei.com/pop/能匹配上http://www.huawei.com/test/Huawei.jsp能匹配上http://www.web.huawei.com/test/a.jsp?v=huawei不能匹配上2.文件结尾的，认为此请求为一个文件的请求，而不认为是一个路径。例：配置规则http://chaotex.i139.cn/DP/SDGEThttp://chaotex.i139.cn/DP/SD能匹配上GEThttp://c

5、haotex.i139.cn/DP/SD/a.html匹配不上GEThttp://chaotex.i139.cn/DP/SD.jsp匹配不上3.路径带“/”结尾，路径后带”/”表示此条配置为一个路径，路径后面可以带有更多的路径及文件都能够匹配上。例：配置规则http://wap.ziyitong.com/Temporary/http://wap.ziyitong.com/Temporary/aa/aaaa/aa/匹配上http://wap.ziyitong.com/Temporary/aa/aaaa/aa/

6、c匹配上域名中带有通配符1.支持域名前后带*的情况:http://*.huawei.com,http://www.huawei.*,http://*.huawei.*，但是*可以匹配N段域例：配置：http://*.huawei.comhttp://www.huawei.com能匹配上http://www.web.huawei.com能匹配上配置规则:http://www.huawei.*http://www.huawei.com能匹配上http://www.huawei.com.cn能匹配上配置规则:ht

7、tp://*.huawei.*http://www.huawei.com能匹配上http://www.huawei.com.cn能匹配上http://www.web.huawei.com能匹配上2.域名或ip地址后面加”/”和不加”/”效果一样例：配置规则http://www.huawei.com和http://www.huawei.com/效果一样3.ip地址的通配，支持http://*.164.102.107和http://10.164.102.*即首尾通配的情况例：配置规则http://*.164.1

8、02.107http://10.164.102.107能匹配上配置规则http://10.164.102.*http://10.164.102.107能匹配上域名中的通配符的约束：Ø只能替换以“.”分隔的字符串，不能替换符号“.”以及包含该符号的字符串Ø只能替换域名中以“.”分隔的第一个和最后一个字段Ø通配符不能替换URL规则定义中的端口号，不能替换符号Ø不支持http://*.*.*等多个*的匹配Ø不支持htt