• 贪心算法☞磁带最优存储问题


    题目描述

    设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li, 1<= i<= n。这n 个程序的读取概率分别是p1,p2,...,pn,且pi+p2+...+pn = 1。如果将这n 个程序按 i1,i2,....,in 的次序存放,则读取程序ir 所需的时间tr=c*(Pi1*Li2+Pi2*Li2+...+Pir*Lir)。这n 个程序的平均读取 时间为t1+t2+...+tn。 磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序,使平均读取时间达到 最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。 编程任务: 对于给定的n个程序存放在磁带上的长度和读取概率,编程计算n个程序的最优存储方 案。
    输入 由文件input.txt给出输入数据。第一行是正整数n,表示文件个数。接下来的n行中, 
    每行有2 个正整数a 和b,分别表示程序存放在磁带上的长度和读取概率。实际上第k个程 
    序的读取概率ak/(a1+a2+...+an)。对所有输入均假定c=1。


     

    #include 
    #include 
    /*
    磁带最优存储问题。
    有n个程序存放在长度L的磁带,读取概率为p。读取程序时间 t = l*p
    要求确定程序在磁带上的次序,使平均读取事件最小。
    */
    #define SIZE 100
    float   B[SIZE];
    struct tap
    {
        int a;     //程序长度
        int b;     //读取概率
    }A[SIZE];
    
    void  sort(float B[],int n);
    float greedy(struct tap A[],int n);
    
    int main()
    {
        int i ,n;
        printf("请输入程序个数:\n");
        scanf("%d",&n);
        printf("请输入程序长度和读取概率\n");
        for(i = 0;i < n;i++){
            scanf("%d",&A[i].a);
            scanf("%d",&A[i].b);
        }
        printf("平均读取时间最小为:%f",greedy(A,n));
        return 0;
    }
    void sort(float B[],int n)
    {
        int i,j,temp;
        for(i = 0;i B[j])
                {
                    temp = B[i];
                    B[i] = B[j];
                    B[j] = temp;
                }
            }
        }
    }
    float greedy(struct tap A[],int n)
    {
        int i,sum =0;
        float time = 0;
        for(i = 0;i < n; i++)
        {
        B[i] = A[i]. b*A[i].a;    //计算p*l乘积
        sum += A[i].b;            //对输入的概率求和
        }
        sort(B,n);                //按p*l由小到大排序
    
        for(i = 0;i < n; i++)
        {
           time += (n-i)*B[i];    /*5*B[0]+4*B[1]+3*B[2]+2*B[1]+B[0]*/
        }
        return time/sum;
    }
  • 相关阅读:
    AcWing 4507. 子数组异或和
    javacc之路3---CharStream
    没想到吧,Spring中还有一招集合注入的写法
    【ROS】机械人开发四--ROS常用概念与Launch文件
    看了就能懂的NIO使用深入详解
    【C++】 —— string的使用
    HummerRisk 快速入门教程
    TCP网络编程入门
    初阶指针(1)
    14. 类
  • 原文地址:https://blog.csdn.net/m0_72429728/article/details/128010820