#include?
#include?
using?namespace?std;

int?*array*x*bestxCbestp;

//回溯法
void?backtrack（int?iint?cpint?cw）
{?
????int?j;
????if（i>array[0]）
????{
????????if（cp>bestp）?
????????{
????????????bestp=cp;
????????????for（i=0;i<=array[0];i++）?
				bestx[i]=x[i];
????????}
????}
????else?
????????for（j=0;j<=1;j++）??
????????{
????????????x[i]=j;
????????????if（cw+x[i]*array[i]<=C）???
????????????{
????????????????cw+=array[i]*x[i];
????????????????cp+=array[i]*x[i];
????????????????backtrack（i+1cpcw）;
????????????????cw-=array[i]*x[i];
????????????????cp-=array[i]*x[i];
????????????}
????????}
}


void?distribution（int?*?Array?int?*?ArrayA?int?*?ArrayBint*x）//將程序分配到AB集合中
{
	backtrack（100）;
	ArrayA[0]?=?0;						//將集合AB初始化為空
	ArrayB[0]?=?0;
	for（int?i?=?1;?i?<=?Array[0];?i++）
	{
		if（bestx[i]?==?1）
		{
			ArrayA[++ArrayA[0]]?=?Array[i];
		}
		else
		{
			ArrayB[++ArrayB[0]]?=?Array[i];
		}
	}
}
?
//主函數
void?main（）
{
	cout<<“**********************************回溯法*********************************“<	cout<
	int?n;//程序的數目
	int?*arrayA;?//存放分配后的程序
	int?*arrayB;
	int?sum;//存放程序的長度
	sum=?0;?
	
	cout<<“請輸入程序數目：“<????cin>>n;
????array?=?（int?*）malloc（（n+1）*sizeof（int））;//動態申請空間
????arrayA?=?（int?*）malloc（（n+1）*sizeof（int））;
????arrayB?=?（int?*）malloc（（n+1）*sizeof（int））;
????x=?（int?*）malloc（（n+1）*sizeof（int））;
????bestx?=?（int?*）malloc（（n+1）*sizeof（int））;
????bestp=0;?
????
	cout<
????cout<<“******************************未分配前*************************************“<????array[0]?=?n;
????cout<<“請依次輸入程序段長度：“<????for（int?i=1;?i<=array[0];?i++）
????{
		cout<<“第“<????	cin>>array[i];
????	sum?+=array[i];
????}
	C?=?sum/2;
	cout<
????distribution（arrayarrayAarrayBx）;

	cout<<“******************************分配后**************************************“<????//顯示A組分配到的程序的其長度
????cout<<“A組分配到的程序段長度組：“<????for（int?j=1;?j<=arrayA[0];?j++）
????{
????	cout<????}
????cout<
	//顯示B組分配到的程序的其長度
????cout<<“B組分配到的程序段長度組：“<????for（int?k=1;?k<=arrayB[0];?k++）
????{
????	cout<????}
????cout<????
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2013-12-30?16:02??huisufa\
?????目錄???????????0??2013-12-30?16:00??huisufa\Debug\
?????文件???????74752??2013-12-30?16:01??huisufa\Debug\vc60.idb
?????文件??????110592??2013-12-30?16:00??huisufa\Debug\vc60.pdb
?????文件??????544831??2013-12-30?16:00??huisufa\Debug\回溯法.exe
?????文件??????786816??2013-12-30?16:00??huisufa\Debug\回溯法.ilk
?????文件??????251454??2013-12-30?16:00??huisufa\Debug\回溯法.obj
?????文件?????2010972??2013-12-30?16:00??huisufa\Debug\回溯法.pch
?????文件?????1090560??2013-12-30?16:00??huisufa\Debug\回溯法.pdb
?????文件????????2409??2012-12-12?21:59??huisufa\回溯法.cpp
?????文件????????3403??2013-12-30?16:00??huisufa\回溯法.dsp
?????文件?????????520??2013-12-30?16:00??huisufa\回溯法.dsw
?????文件???????41984??2013-12-30?16:02??huisufa\回溯法.ncb
?????文件???????48640??2013-12-30?16:02??huisufa\回溯法.opt
?????文件?????????246??2013-12-30?16:01??huisufa\回溯法.plg