求解分枝定界算法
问题:有I种类型的矩形件,第I种类型的矩形件数量为Ni,其长度为Li,宽度为Wi,现给定一个更大的宽度值W(0 < Wi <= Li <W),要求在这些矩形件中找到边长相同的合并起来组成一个大的矩形件,使大矩形件的一边满足条件
W % (a1*x1+a2*x2+.....+ai*xi) 最小.(其中a1是第一种矩形件的长或宽,x1表示用到x1个第1种矩形件,以此类推,ai是第i种矩形件的长或宽,xi表示用到xi个第i种矩形件).当中W、Wi、Li、ai、xi都为非负整数.
上面是一个整数规划问题，如何用分枝定界法描述出来呀?我对这个算法没理解透，写不出。
多谢好心大侠帮忙了。
[解决办法]
分枝定界一般是相对于盲目回溯算法而言的，也就是去除无意义的树状分枝，因此只要你在回溯算法的基础上加上合理的if一类的条件来限制使其不成生或是少生成分枝，就算是运用了分枝定界的算法，也正此因，一个初学者的分枝定界与一个高手的分枝定界的算法效率可能相差很大。与其说分枝定界是一种算法还不如说是一种相对最低级回溯算法的优化，即一种思想，你试着理解着改一改吧，最体的你可以看看对背包问题的分枝定界，这个例子很常见的，你搜一下就可以了
[解决办法]
来晚了,对于问题规模为n的,一般裸回溯就会产生2^n的状态空间,形成2^n个节点的完全二叉树,分支定界就是所谓的剪枝,把有些不可能的分支剪掉而已,因此思想很简单.
其实lz的这个问题感觉就是0-1背包的延伸,祝lz好运
