算法设计之回溯法

把长度为l1,l2…ln 的n个程序放在磁带T1和T2上，并且希望按照使用最大检索时间取得最小值的方式存储，即如果存放在T1和T2上的程序集合分别为A和B，则希望所选择的A和B使得max{∑li 1,∑li2}(i1属于A，i2属于B)取得最小。 使用回溯法实现。

#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