1.问题

2.解析

定理：如果装载问题有解，则存在一个使得第一条船装载量与的差达到最小的解。

(1)首先将第一艘轮船尽最大可能装满；
(2)然后将剩余的集装箱装上第二艘轮船。
采用回溯算法：设集装箱的重量分别为：W={90，80，40，30，20，12，10},c1 = 152,c2 = 130

3.设计

void backtrack(int t,int c){
if(t>n){
if(cw>bestcw){
bestcw=cw;
for(int i=1;i<=n;i++){
bestx[i]=x[i];
}
}
else return;
}else{
if(cw+w[t]<=c){//搜索左子树
cw+=w[t];
x[t]=1;
backtrack(t+1,c);
cw-=w[t]; //还原
x[t]=0;//返回上一层是两个都还原
}else{
x[t]=0;
backtrack(t+1,c);//搜索右子树
}
}
}

4.分析

最坏情况要遍历图中所有结点，算法的时间复杂度为O(2n)。因为，叶子结点有2n，每个结点要计算机装载量以判断是否回溯。

5.源码

https://github.com/joserfdave/arithmetic/tree/main