算法分析和设计贪心法.ppt

可行解的确定 定理3.3: 设J是k个作业的集合=i1,i2,ik是J中作业的一种排列它使得di1di2dikJ是一个可行解当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况来处理 定理3.2 证明 证明 充分性若J中的作业可以按照的次序而又不违反任何一个期限的情况来处理则J就是一个可行解 必要性由于J可行则必存在一种调度序列=r1r2rkdrjj1j k 假设 则a是使得ra ia的