#include????
using?namespace?std;??
??
typedef?int*?pINT;??
template??
class?Loading{??
public:??
???????????friend?Type?MaxLoading（Type*?wint?num?Type?C1int*?bestx?）;??
???friend?void?SolveLoading（int?C2bool*?xint*?wint?num）;??
?
????void?Backtrack（int?i）;??
??
????int?num;/*?集裝箱數目?*/??
????int?*?x;/*?當前解?*/??
????int?*?bestx;/*?當前最優解?*/??
??????Type*?w;/*?集裝箱重量數組?*/??
????Type??C1;/*?第一艘船的容量?*/??
????Type?cw;??
????Type?bestw;??
???Type?r;/*?剩余集裝箱重量?*/??
};??
?
template??
void?Loading::Backtrack（?int?i?）??
{??
???if（?i?>?num）{??
????????if?（?cw?>?bestw?）?{??
???????????for?（int?i?=?1;?i?<=?num?;?i++?）?{??
????????????????bestx[i]?=?x[i];??
????????????????bestw?=?cw;???????????????
????????????}??
????????}??
????????return?;??
???}??
???r?-=?w[i];??
???if?（?cw+w[i]?<=?C1?）?{??
???????x[i]?=?1;??
???????cw?+=?w[i];??
???????Backtrack（i+1）;??
???????cw?-=?w[i];??
????}??
?
????if?（?cw+r?>?bestw?）?{??
???????x[i]?=?0;??
????????Backtrack（i+1）;??
????}??
??
????r?+=?w[i];??
??
}??
template??
Type???MaxLoading（?Type*?wint?num?Type?C1int*?bestx?）??
{??
???Loading?X;??
???X.x?=?new?int[num+1];??
????X.w?=?w;??
????X.C1=?C1;??
????X.num?=?num;??
????X.bestx?=?bestx;??
????X.bestw?=?0;??
????X.cw?=?0;??
????X.r?=?0;??
????for?（int?i?=?1;?i?<=?num?;?i++?）?{??
???????X.r?+=?w[i];??
????}??
???X.Backtrack（1）;??
????delete[]?X.x;??
????return?X.bestw;??
??
}??
template??
?void????SolveLoading（?int?C2int*?xType*?wint?num?）??
?{??
?????int?totalW?=?0;??
?????int?c1W?=?0;/*?第一艘船總載重?*/??
?????for?（int?i?=?1;?i?<=?num?;?i++?）?{??
?????????if?（?x[i]?==?1?）?{??
?????????????c1W?+=?w[i];??
?????????}???
?????????totalW?+=?w[i];??
?????}??
?????if?（?totalW-c1W?>?C2?）?{??
?????????printf（“沒有合理的裝載方案!?:（?“）;??
?????????return;??
?????}??
??
?????printf（“?裝載方案如下:\n?“）;??
?????printf（“?第一艘船裝?“）;??
????for?（int?i?=?1;?i?<=?num?;?i++?）?{??
????????if?（?x[i]?==?1?）?{??
?????????????printf（“%d?“i）;??
?????????}???
?????}??
?????printf（“\n總載重?%d?\n“c1W）;??
??
??
?????printf（“?第二艘船裝?“）;??
?????for?（int?i?=?1;?i?<=?num?;?i++?）?{??
?????????if?（?!?x[i]?）?{??
?????????????printf（“%d?“i）;??
??????????????????????}???
???????????????????????????}??
?????printf（“\n總載重?%d?\n“totalW-c1W）;??
??
}??
??
int?main（int?argcchar*?argv[]）{??
??
????int?C1?=?0;??
????int?C2?=?0;??
????int?num?=?0;??
????int*?x?=?NULL;??
????int**?m?=?NULL;??
????int*?w?=?NULL;??
??
????printf（“輸入第一艘船最大載重量:“）;??
????scanf（“%d“&C1）;??
??
????printf（“輸入第二艘船最大載重量:“）;??
????scanf（“%d“&C2）;??
??
??
????printf（“輸入貨物個數“）;??
????scanf（“%d“&num）;??
??
????x?=?new?int[num+1];??
????w?=?new?int[num+1];??
????m?=?new?pINT[num+1];??
????for?（int?i?=?0;?i?????????m[i]?=?new?int[num+1];??
????}??
??
??
????printf（“分別輸入貨物重量（回車結束）：\n“）;??
??
????for?（int?i?=?1;?i?<=?num?;?i++?）?{??
???

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????34972??2012-05-22?17:33??裝載問題回溯算法\裝載問題回溯算法.docx

?????文件???????3348??2012-05-22?17:23??裝載問題回溯算法\zzhs.cpp

?????文件?????477406??2012-05-22?17:31??裝載問題回溯算法\zzhs.exe

?????目錄??????????0??2012-05-22?17:34??裝載問題回溯算法

-----------?---------??----------?-----??----

???????????????515726????????????????????4