一般解题步骤分为三步:
- 针对所给問题,定义问题的解空间
- 确定易于搜索的解空间结构(一般为子集树或者排列树)
- 以深度优先的方式搜索解空间,并且在搜索过程中用减枝函数避免无效搜索
1.其中子集树就是选一部分,比如0-1背包问题,装载问题;
2.而排列树就是选所有,只是顺序不一样,例如旅行商(邮递员)问题.
假设装载的集装箱n=3则空间树可以表示为上图，1表示装入该集装箱0表示不装入该集装箱，最优装载问题就是在这些空间树里寻找最优解。
已知n个集装箱,輪船载重量为c,集装箱i的重量为Wi,要求是在不超重的情况下,装尽可能多数量的集装箱.
注意： 有两个轮船时,以下代码用于轮船1,而轮船2用于放置剩餘的集装箱
- 首先将轮船1尽可能装满
- 然后将剩余的集装箱装上轮船2
#define NUM 100 //注意，因为没有用类所以这些变量需要均写在外面。
//形参代表搜索第t層节点,从1开始
//如果当前载重量加上剩余集装箱的重量没有超过前一个最优装载量的话就不用考虑了
r+=w[t]; //返回时还原剩余集装箱重量
