把长度为l1,l2…ln 的n个程序放在磁带T1和T2上,并且希望按照使用最大检索时间取得最小值的方式存储,即如果存放在T1和T2上的程序集合分别为A和B,则希望所选择的A和B使得max{∑li 1,∑li2}(i1属于A,i2属于B)取得最小。
使用回溯法实现。
代码片段和文件信息
属性 大小 日期 时间 名称
----------- --------- ---------- ----- ----
目录 0 2013-12-30 16:02 huisufa
目录 0 2013-12-30 16:00 huisufaDebug
文件 74752 2013-12-30 16:01 huisufaDebugvc60.idb
文件 110592 2013-12-30 16:00 huisufaDebugvc60.pdb
文件 544831 2013-12-30 16:00 huisufaDebug回溯法.exe
文件 786816 2013-12-30 16:00 huisufaDebug回溯法.ilk
文件 251454 2013-12-30 16:00 huisufaDebug回溯法.obj
文件 2010972 2013-12-30 16:00 huisufaDebug回溯法.pch
文件 1090560 2013-12-30 16:00 huisufaDebug回溯法.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
#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 huisufaDebug
文件 74752 2013-12-30 16:01 huisufaDebugvc60.idb
文件 110592 2013-12-30 16:00 huisufaDebugvc60.pdb
文件 544831 2013-12-30 16:00 huisufaDebug回溯法.exe
文件 786816 2013-12-30 16:00 huisufaDebug回溯法.ilk
文件 251454 2013-12-30 16:00 huisufaDebug回溯法.obj
文件 2010972 2013-12-30 16:00 huisufaDebug回溯法.pch
文件 1090560 2013-12-30 16:00 huisufaDebug回溯法.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
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件举报,一经查实,本站将立刻删除。
评论列表(条)