`
niyayu
  • 浏览: 33580 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

#贪心算法(零件加工)

 
阅读更多
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 1001

struct strTime
{
int nStart;
int nEnd;
};
strTime strLing[MAX],strMach[MAX];

void vInit();
void vInput(int n);
void vSort(int n);
bool cmp(const strTime &strA,const strTime &strB);
int nFind(int nM,int nMaxM);
int nGetNum(int n);
void vPutout(int numM);

int main()
{
int nNum;
int nNumMach;

while(1==scanf("%d",&nNum))
{
vInit();
vInput(nNum);
vSort(nNum);
nNumMach=nGetNum(nNum);
vPutout(nNumMach);

}
return 0;
}


void vInit()
{
memset(strLing,0,sizeof(strLing));
memset(strMach,0,sizeof(strMach));
}

void vInput(int n)
{
int i;
for(i=0;i<n;i++)
{
scanf(" [%d,%d]",&strLing[i].nStart,&strLing[i].nEnd);
}
}

void vSort(int n)
{
sort(&strLing[0],&strLing[n],cmp);
}

bool cmp(const strTime &strA,const strTime &strB)
{
if(strA.nStart==strB.nStart)
return(strA.nEnd<strB.nEnd);
return(strA.nStart<strB.nStart);
}

int nFind(int nM,int nMaxM)
{
int i;
for(i=0;i<nMaxM;i++)
{
if(strLing[nM].nStart>=strMach[i].nEnd)
return i;
}
return i;
}

int nGetNum(int n)
{
int i;
int nRet;
int temp;

nRet=0;
for(i=0;i<n;i++)
{
temp=nFind(i,nRet);
if(temp<nRet)
{
strMach[temp].nEnd=strLing[i].nEnd;
}
else
{
nRet++;
strMach[temp].nEnd=strLing[i].nEnd;
strMach[temp].nStart=strLing[i].nStart;
}
}
return nRet;
}

void vPutout(int numM)
{
printf("%d\n",numM);
}
分享到:
评论

相关推荐

    贪婪算法例子-零件加工

    ### 贪婪算法在零件加工中的应用 #### 问题背景 题目中提到的问题是关于一个国有中型企业接收到的一批零件加工订单。该企业面临的主要挑战在于:它需要完成这批订单,但又不想为此投入过多成本去购置新机床。为了...

    数学实验编程

    在实际编程过程中,可能需要使用动态规划或贪心算法等优化策略来寻找最优解。在给定的例子中,最优的零件排序为G-I-D-H-J-E-A-F-C-B,对应的总加工时间为425分钟。 当引入额外条件,如零件D必须在E之前加工,H与J...

    复杂曲面零件的在线检测路径规划方法研究 (2010年)

    在线检测技术可以实现曲面零件特别是大型复杂零件加工精度的快速检测,能避免产生因二次装夹而出现的重定位误差。笔者针对在线检测技术的关键问题--检测路径规划开展研究,提出了基于零件三角网格模型测点法矢方向的...

    全国大学生数学建模竞赛试题

    - 使用动态规划、贪心算法等方法寻求最优解。 3. **特定准则评价**: - 对于“每次选择一个加工费用最少的待切割面进行切割”的准则,虽然在某些情况下可以有效降低总费用,但在其他情况下可能会导致更高的总成本...

    排料软件,原材料裁剪优化

    算法可能会采用动态规划、贪心策略或者遗传算法等方法,通过计算机模拟和计算,找到最优解。在处理大量数据和复杂形状时,高效的算法至关重要。 角钢排料是软件的一个特定应用领域。角钢作为一种常见的建筑和结构...

    UG\NX二次开发 代工分享的“单个体XY排料工具”源码完整版

    2. **算法实现**:采用合适的优化算法(如贪心算法、遗传算法或模拟退火)来排列零件,确保在有限的XY平面上实现最小面积覆盖。 3. **约束处理**:考虑零件之间的间隙、方向限制、对齐方式等因素,确保排料方案满足...

    第9章-作业排序问题.pdf

    这些方法包括优先级规则、贪心算法、模拟退火、遗传算法、动态规划等。实际应用中,往往需要在计算复杂性和解质量之间找到一个平衡点,以适应不同的业务需求和环境变化。 总的来说,作业排序问题在工业生产、物流...

    生产作业排序的问题.pptx

    - **工件(Job)**:被处理的对象,如加工的零件或需要维修的设备。 - **机器(Machine)**:提供服务的设备,可以是加工设备或工人。 - **作业计划(Scheduling)**:不仅包括排序,还涉及每个工件在每台机器上...

    code.rar_排样_排样优化_矩形 排样 优化_矩形 排样优化_矩形件排样

    此外,为了提高算法效率,可能还会使用到数据结构和算法,如贪心算法、动态规划或遗传算法等。这些方法可以帮助快速找到近似最优解,同时保持计算时间在可接受范围内。 总之,这个压缩包内容涉及到的是一个用于矩形...

    历年NOIP(普及组)难度与考点分析

    4. **贪心策略**:在部分题目中,通过局部最优决策来达到全局最优,如2000年的"旅行家的预算"、2004年的"花生采摘"和2019年的"CSP-J加工零件"。 5. **字符串处理**:涉及到字符串的比较、操作和模式匹配,如1998年...

    PGM的nesr++2

    1. **智能算法**:采用先进的算法,如遗传算法、贪心算法或深度学习模型,来寻找最优的物料排布方案。 2. **自适应调整**:能够根据不同的物料形状、大小和数量,动态调整排布策略,确保最佳利用率。 3. **实时优化*...

    全国数学建模竞赛的题目

    可以使用贪心算法、动态规划或者近似算法来求解。题目的变体还考虑了不同的停留时间和行驶速度,以及如何在有限的组数下尽快完成任务。 1997A题涉及参数设计,这是工程优化的一个方面。产品性能依赖于各个零件的...

Global site tag (gtag.js) - Google Analytics