//============================================================================
磁带最优存储问题：设有n个程序{1，2，……n }要存放在长度为L的磁带上。程序i 存放在磁带上的长度是li ，1<=i<= n。这n个程序的读取概率分别为p1，p2，…… pn，且
Σpi=1(i=1,2,….n)。如果将这n个程序按i1，i2，…… in的次序存放，则读取程序所需的时间
tr=cΣpik lik(k=1,2,….r)（可假定c为1）。这n 个程序的平均读取时间为t(1)+t(2)+...+t(r)。磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到最小。
//============================================================================
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
/**
* Program 表示磁带上的一个程序
*/
class Program{
public:
float l; // 长度
float p; // 运行的概率
float c; // 运行的次数
Program(){
}
/**
* 得到长度和概率的乘积
*/
float mult(){
return l*p;
}
/**
* 设置长度和运行的次数
*/
void set(float length, float count){
l = length;
c = count;
}
/**
* 将另一个程序的参数复制到本程序中
*/
void set(Program* other){
p = other->p;
c = other->c;
l = other->l;
}
};
/**
* 计算排列顺序的函数
*/
float greedy(Program* programs, int num){
float totalTime = 0;
int i=0;
Program* temp = new Program();
for(i=0;i<num;i++){
Program* smallest = &programs[i]; //每次取p*l最小的一个程序排在磁带的前面
for(int j=i;j<num;j++){
Program* prog = &programs[j];
if(prog->mult() < smallest->mult()){
// 交换smallest 和 temp
temp->set(smallest);
smallest->set(prog);
prog->set(temp);
}
}
totalTime += (num-i) * programs[i].mult();
// 这是n个程序的平均读取时间的计算公式，
// n * 第一个程序的长度 * 第一个程序的长度概率 +
// （n-1） * 第二个程序的长度 * 第二个程序的长度概率 +
// ... ...
// 1 * 最后一个程序的长度 * 最后一个程序的长度概率；
}
return totalTime;
}
int main() {
int num, l, c;
ifstream inFile ("input.txt");
if (inFile.is_open()){
inFile >> num; // 从输入文件中读取输入
Program* programs = new Program[num];
int i = 0;
while (! inFile.eof() ) {
inFile >> l;
inFile >> c;
programs[i].set(l, c);
i++;
}
inFile.close();
float totalCount = 0;
for(i=0;i<num;i++){
totalCount += programs[i].c; // 累加所有程序的总运行次数
}
for(i=0;i<num;i++){
Program* prog = &programs[i];
prog->p = prog->c/totalCount; // 根据输入计算每个程序运行的概率
}
float totalTime = greedy(programs, num);
cout << totalTime << endl;
ofstream outFile; // 将结果写到输出文件中
outFile.open ("output.txt");
outFile << totalTime;
outFile.close();
return 0;
} else{
cout << "Unable to open file";
return 0;
}
}