| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 95 人关注过本帖
标题:用贪心法求解最小服务等待时间
只看楼主 加入收藏
陈春
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2019-11-18
结帖率:0
  已结贴   问题点数:20  回复次数:1   
用贪心法求解最小服务等待时间
设有n个顾客同时等待一项服务,顾客i 需要的服务时间为ti  ,i=1,2,3,…,n 。从时刻0开始计时,若在时刻t开始对顾客i服务,那么i的等待时间为t,应该怎么安排n个顾客的服务次序使得总的等待时间(每个顾客等待时间的总和)最少?
假设服务时间分别为{1,3,2,15,10,6,12},用贪心算法给出这个问题的解。
#include <stdio.h>
#include <string.h>
#define SIZE 10
int A[SIZE];
int B[SIZE];
void sort(int A[],int n);
double greedy(int A[],int n);
void swap(int * a,int * b);
int  main()
{
        int n,i;// n个顾客
        printf("请输入顾客数:\n");
        scanf("%d",&n);
        printf("请输入每个顾客的服务时间:\n");
        for(i = 1;i<=n;i++)
        {
         
            scanf("%d",&A[i-1]);
            B[i]=A[i-1];
       }
       sort(A,n);
       printf("服务的次序为:\n");
       for(int j=0;j<n;j++)
           for(i=1;i<=n;i++)
               if(A[j]==B[i])
                   printf("%3d",i);
       printf("\n");
       printf("\n等待时间的总和最小为:%.2f",greedy(A,n));
       return 0;
}
double greedy(int A[],int n)
{
    int i,time = 0;
    for(i = 0;i < n;i++)
    {   printf("%3d",time);
        time = time +(n-i)*A[i];
        
    }
    return time;
}
void sort(int A[],int n)
{
    int i,j;
    for(i = 0;i < n;i++)
    {
        for(j = i+1;j < n;j++)
        {
            if(A[i] > A[j])
            swap(&A[i],&A[j]);
        }
    }
}
void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
假设原问题为T(先假设只有一个服务点),而我们已经知道了某个最优服务系列,即最优解为A={t(1),t(2),….t(n)}(其中t(i)为第i个用户需要的服务时间),
则每个用户等待时间为:
T(1)=t(1);
T(2)=t(1)+t(2);

T(n)=t(1)+t(2)+t(3)+…+t(n);
那么总等待时问,即最优值为:
TA=n*t(1)+(n-1)*t(2)+…+(n+1-j)t(i)+…+2t(n-1)+t(n);

有点疑惑:为啥那个算等待时间的时候最开始不是等待时间为0
还有就是怎么修改求出每个服务的等待时间啊


























搜索更多相关主题的帖子: 服务 int 时间 for printf 
【推荐】大型监控、工控、组态VC++./C#源码组件库2019下载!
【推荐】超50万数控、建模仿真、电力VC++/.NET图形源码库下载!
【推荐】专业CAD\GIS\业务流程VC++/C#可视化图形软件源码库下载!
2019-11-18 20:26
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:334
帖 子:6899
专家分:40123
注 册:2011-1-18
  得分:20 
题目就这么一点点吗?连样例输入、样例输出都没有?看不懂呀

用贪心算法给出这个问题的解。 ------ 为什么要用贪心算法,难道不是按照服务时间 从小到大 的顺序服务?

为啥那个算等待时间的时候最开始不是等待时间为0 ------ 那我猜它要求的等待时间 是指 从 等待开始处理的时间+处理时间
2019-11-19 09:09
快速回复:用贪心法求解最小服务等待时间
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.148383 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved