程序存储问题.cpp

程序存储问题:设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li

/*程序存储问题
问题描述：
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li ，1≤i≤n; 
程序存储问题要求确定这n 个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。
编程任务： 
对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。 
数据输入：由文件input.txt给出输入数据。第一行是正整数n，表示文件个数。接下来的1 行中，有n个正整数，表示程序存放在磁带上的长度。  
结果输出: 
input.txt           output.txt 
6  50                     5
2 3 13 8 80 20 
*/
#include<iostream.h>
#include<fstream.h>

void run(unsigned long* pData,int left,int right) 
{ 
  int i,j; 
  unsigned long middle,iTemp; 
  i = left; 
  j = right; 
  middle = pData[(left+right)/2]; //求中间值 
  do{ 
     while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 
       i++; 
     while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 
       j--; 
     if(i<=j)//找到了一对值 ,交换 
	 { iTemp = pData[i]; 
	   pData[i] = pData[j]; 
	   pData[j] = iTemp; 
	   i++; 
	   j--; 
	} 
  }while(i<=j);//如果两边扫描的下标交错，就停止（完成一次） 
 if(left<j)   //当左边部分有值(left<j)，递归左半边  
   run(pData,left,j); 
 if(right>i)//当右边部分有值(right>i)，递归右半边  
   run(pData,i,right); 
} 

void sort(unsigned long* pData,int Count) //使用快速排序进行排序;
{ 
   run(pData,0,Count-1); 
} 


int Prog(unsigned long *a,int n,unsigned long lenght)//计算程序存储数量函数;
{ int count=0;
  
  for(int i=0;(i<n)&&(a[i]<=lenght);i++)
  { 
	 count++;
	 lenght-=a[i];
  }
  return count;
}


void main()
{ int n,count;
  unsigned long lenght;
  ifstream myin;
  myin.open("input.txt",ios::nocreate);
  if(!myin) 
  { cout<<"The file input.txt cannot open,Please check it again!"<<endl;
	return;
  }
  myin>>n;
  myin>>lenght;
  
  unsigned long *len=new unsigned long[n];
  for(int i=0;i<n;i++)
	  myin>>len[i];
  sort(len,n);
  count=Prog(len,n,lenght);
  ofstream myout("output.txt");
  myout<<count;
  myout.close();
  myin.close();

}