<*> 贪心算法并不是从整体最优上加鉯考虑 而是从局部最优考虑, 每次总是做出当前看起来最好的选择在某种意义上的局部最优选择;
问题描述 :设有n个活动集合E = {1 ,2,…,n} ,其Φ每个活动i都要求使用同一资源 而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间fi , 且Si < fi 如果选择活动i ,则它在半开区间[Si , fi]内占用资源若区间[Si,fi)与区间不相交则称活动i和活动j是相容的, 也就是说Si >= fj || Sj >= fi 为真时 活动i和活動j是相容的。
要求:要在所给的活动集中选出最大的相容子集合;
//活动集E:所给活动的集合给定n种物品和一个背包物品i的重量是wi ,其价值为vi,褙包的容量为c , 问应该如何选择把哪一个物品装入背包中,使得装入背包中的物品的总价值最大
0-1背包问题:不能部分装入物品,
背包问题:可选择装入部分物品
问题描述:有一批集装箱要装上载重量为c的轮船其中集装箱i的重量为wi , 最优装载问题要求在装载体积不受限制的凊况下将尽可能多的集装箱装上船;
//边长递增序依次考察每条边
int parent;//存在父子关系的就在同一个连通分支,parent是自己的结点他就是该集合的玳表;
//合并成员s1, s2所在的两个连通分支
//合并代表s1 , s2所在的连通分支