福州建站免费模板,wordpress搭建后域名打不开,计算机软件开发流程,徐州市做网站贪心算法的设计技术 • 每一步的判断都是一个当前最优的抉择#xff0c;这个抉择计算设计的好坏#xff0c;决定了算法的成败。 • 多步判断过程#xff0c;最终的判断序列对应于问题的最优解 • 适用于 能够 由 局部最优达到全局最优的优化问题 【比如 求最短哈密顿回路的…贪心算法的设计技术 • 每一步的判断都是一个当前最优的抉择这个抉择计算设计的好坏决定了算法的成败。 • 多步判断过程最终的判断序列对应于问题的最优解 • 适用于 能够 由 局部最优达到全局最优的优化问题 【比如 求最短哈密顿回路的问题就不是】 • 需要对具体的贪心算法的正确性进行必要的证明 用贪心法 求问题的解 【例7-1】 学生有n项活动申请使用某一个会议室每项活动都有一个开始时间和一个结束时间。任何两个活动都不能同时使用这个会议室。问如何安排这些活动使得被安排活动的数量达到最多 问题分析 设活动编号的集合为A{1,2,…,n}第i项活动的起始时间为si 结束时间为e i 。满足s i ≥e j 或s j ≥e ii≠j称为活动相容。 求A的两两相容的最大活动子集S。 方法1按活动开始时间优先【更早的开始活动也许能安排更多的活动】例 A{1,2,3}s 1 0, e 1 17, s 2 3,e 2 5,s 3 8,e 3 15 方法2按占用时间由短到长来选择也许可能安排更多的活动 例A{1,2,3}s 1 0, e 1 8, s 2 7,e 2 10,s 3 9,s e 15 方法3按结束时间从小到大选择也许可以安排更多的活动。 命题 活动是按结束时间从小到大进行排序的即有 e 1 ≤e 2 ≤e 3 …≤e n 贪心算法选择到第k步有k项活动被选择 生成一个选择序列i 1 ,i 2 , …,i k 按策略必有i 1 1 那么最优解S必然包含i 1 ,i 2 , …,i k 。 【全局最优包含局部最优】 证明设A中的活动都是按照结束的时间递增的顺序排列的 S是A的最优解且S{i 1 ,i 2 , …,i m }。 (1) 当k1时需证明活动1被包含在最优解S中即i 1 1。 假设 i 1 ≠1那么用活动1去替换i 1 得到S’有S’(S-{i 1 } ) ∪{1} 因为活动1结束时间比i 1活动结束得更早因此其和i 2 , …,i m活动均相容又由于S与S’数量相同 所以S’也是A的最优解。 命题成立。 (2)假设对于任意整数k命题正确。 若前k步顺序选择的活动 为i 1 ,i 2 , …,i k 那么存在一个最优解S{i 1 ,i 2 , …,i k }∪B。 如果令S’是S中剩下的与{i 1 ,i 2 , …,ik}相容的活动S’S 那么B是S’的一个最优解。若不然假如S’有解B’B’B那么用B’替换B以后得到解{i1 ,i2 , …,ik}∪B’将比S的活动更多这与S是最优解矛题得证。 对比(1)的证明算法第一步选择结时间最早的活动总是导致一个最优解故对子 问题S’存在一个最优解B*{ i k1 , …}。由于B*与B都是S’的最优解因而B*B。于是 S’{ i 1 ,i 2 , …,i k }∪B*{ i 1 ,i 2 , …,i k , i k1 }∪(B-{ i k1 }) S’与S的活动数目一样多也是一个最优解而且恰好包含了算法前k1步选择的 活动。则命题得证。 1.排序2.相容性判定 计算模型 (1)存储结构 struct Active{startTime s;//开始时间endTime e;//结束时间selectflag f;//选标识
}A[n]; 2计算 活动i 与 活动j 相容 - A[ i ].s A[ j ].e 或 A[ j ].s A[ i ].e 用归并排序 或 其他任何高效的排序算法完成 以a[i].e的从小到大 的排序形成排序A[1].e≤A[2].e ≤…≤A[n].e 【例7-2】数列极差。 给定含有n个正整数的数列a做如下两步操作 (1)每一次删除其中的两个数a i 和a j ; (2)在数列中加入一个数a i ×a j 1 循环执行步骤(1)(2)直到集合中只剩下一个元素为止。 【每种选择顺序会有不同的剩余的数】 设计 算法求得数列中剩余的数为最大值max和最小值min 则该数列的极差为Mmax-min。 问题分析 实例设a{5,6,7}那么它将有三种组织方式 (5*61)*71218 (5*71)*61217 (6*71)*51216。 两个最小的数相乘结果最大。 命题 当一个数列中含有n(n2)数时该数列按数列极差法 求最大数值的方法为每次选择数列中最小的两个数进行相乘加 1。 求最小数值为每次从数列中选择两个最大的数相乘加1。 证明 (1) 当k3时 数列a{a1 , a2 , a3}不妨令a1 a2 a3 这样 可以设a 2 a 1 k 1 (k 1 0)a 3 a 1 k 1 k 2 (k 1 ,k 2 0)。那么这三个数的 三种组合方式为 (a 1 * a 2 1)* a 3 1 a 1 * a 1 * a 1 (2*k 1 k 2 ) *a 1 * a 1 (k 1 *(k 1 k 2 )1)*a 1 k 1 k 2 1 (a 1 * a 3 1)* a 2 1 a 1 * a 1 * a 1 (2*k 1 k 2 ) *a 1 * a 1 (k 1 *(k 1 k 2 )1)*a 1 k 1 1 (a 2 * a 3 1)* a 1 1 a 1 * a 1 * a 1 (2*k 1 k 2 ) *a 1 * a 1 (k 1 *(k 1 k 2 )1)*a 1 1 比较上述三式的同类项可知命题成立 ——思考 A{a1,a2},B{b1,b2,b3}, 设[A][a1 a2]a1*a21 一种值 在运算中{B}{b1,b2,b3}表示三个 顺序 即[b1 b2 b3], [b1 b3 b2], [b2 b3 b1] 若有Aa3Ba4, 试比较 [[A],a3,{B},a4]与 [[A],a4,{B},a3] 猜测[[A],a3,{B},a4] [[A],a4,{B},a3] 因为a3a4 设a4a3k , a3a4-k [[A],a3,{B},a4] [ [A] ,a4-k ,{B} ,a4 ] [ [A]*(a4-k)1 , {B},a4 ] [ [ A,a4]-[A]*k ,{B},a4 ] ——1 B{b1,b2,b3} 取任意一个次序 [[A],a3,{B},a4] ——代入1式 [ [A,a4]-[A]*k ,{ b1, b2,b3,b4},a4 ] [ [A,a4]-[A]*k ,b1, {b2,b3,b4},a4 ] [ ( [A,a4]-[A]*k )*b11 , {b2,b3,b4},a4 ] [ [A,a4,b1] -[A]*k*b1 , {b2,b3,b4},a4 ] ..... [ [A,a4,b1,b2,b3]-[A]*k*b1*b2*b3 ,a4 ] [ [A,a4,b1,b2,b3] *a4 -[A]*k*b1*b2*b3*a4 1] [ [A,a4,b1,b2,b3] *a4 1 -[A]*k*b1*b2*b3*a4 ] 从结果倒推找[[A],a4,{B},a3] 形式 ajaik ,a4a3k , [[A],a3,{B},a4] [ [A,a4,b1,b2,b3] *a4 1 -[A]*k*b1*b2*b3*a4 ] (上文代入a4a3k) [ [A,a4,b1,b2,b3] *(a3k) 1 -[A]*k*b1*b2*b3*a4 ] [ [A,a4,b1,b2,b3] *a3[A,a4,b1,b2,b3]*k 1 -[A]*k*b1*b2*b3*a4 ] [ [A,a4,b1,b2,b3,a3][A,a4,b1,b2,b3]*k -[A]*k*b1*b2*b3*a4 ] [ [A,a4,b1,b2,b3,a3]k*( [A,a4,b1,b2,b3] -[A]*b1*b2*b3*a4 ) ] [ [A,a4,B,a3k] 1 - [A]*k*b1*b2*b3*a4 ] [ [A,a4,B] *(a3k)1 - [A]*k*b1*b2*b3*a4 ] [ [A,a4,B] *a31[A,a4,B] *k - [A]*k*b1*b2*b3*a4 ] [ [A,a4,B,a3] [A,a4,B] *k - [A]*k*b1*b2*b3*a4 ] [ [A,a4,B,a3] k* ( [A,a4,B] - [A]*b1*b2*b3*a4 ) ] 只需比较 [A,a4,B] - [A]*b1*b2*b3*a4 与0 ( [A]*a4 1 )*B1 -[A]*b1*b2*b3*a4 展开或者非常显然 0 因此[[A],a3,{B},a4] [[A],a4,{B},a3] 设A{a1,a2...an} [A,ai] [{a1,a2,...an} ,ai ] [a1,a2,a3...an,ai] [ a1*a21,a3...an,ai] [ ((a1*a2)1 )*a31,....an,ai] [ [A],ai ] (2)假设kn时命题成立。 即在运算过程中每次取序列中两个最小值进行运算最后得到的值为序列的极大值。 令[a i a j ] a i *a j 1则数列a的最大极值 {a n}max[ a1 a2…an ] 。 为了证明kn1成立我们需要先证明一个引理。 ——引理 设有数列集合A和B正整数a i , a j 且有Aa i a j B 其中B{b 1 , b 2 , …b m }{B}表示B中元素的任意组合序列 则有[ [A] , a i , {B}, a j ] [ [A], a j , {B}, a i ]。 引理证明第一个表达式 用第二个表达的出来比较差别 ∵ai aj∵不妨设aj ai k, ai aj – k // k0 ai aj – k [[A], ai, {B}, aj] [[A], aj – k, {B}, aj] [[A]*(aj – k)1, {B}, aj] [[A]*aj –[A]*k1, {B}, aj] [ [A]*aj1 – [A]*k, {B}, aj] [ [A, aj] –[A]*k, {B}, aj] 将B{b1 , b2 , …bm }代入上式并取B的[任意]一个次序 [[A], ai, B, aj] [[A, aj] –[A]*k, b1 ,{ b2 , …bm}, aj] [([A, aj] –[A]*k)*b1 1,{ b2 , …bm}, aj] [ [A, aj] *b1 –[A]*k*b1 1,{ b2 , …bm}, aj] [ [A, aj,b1 ] –[A]*k*b1 ,{ b2 , …bm}, aj] [ [A, aj,b1 ,b2 ,…bm] –[A]*k*b1 * b2 *…*bm, aj] [ ([A, aj,b1 ,b2 ,…bm]–[A]*k*b1 * b2 *…*bm) * aj 1] [ [A, aj,b1 ,b2 ,…bm] * aj–[A]*k*b1 * b2 *…*bm* aj 1] 代入aj ai kB b1,b2,…bm [[A], ai, B, aj] [ [A, aj, B] * (aik)1 –[A]*k*b1* b2*…*bm* aj] [ [A, aj, B] * ai1[A, aj, B] *k –[A]*k*b1* b2*…*bm* aj] [ [A, aj, B, ai] [A, aj, B] *k –[A]*k*b1* b2*…*bm* aj] [ [A, aj, B, ai] k * ([A, aj, B] –[A]*b1* b2*…*bm* aj)] //证明的这个 k * ([A, aj, B] –[A]*b1* b2*…*bm* aj)]0 依据B次序的任意性可得 [[A], a i ,{B}, a j ] [ [A, a j , {B}, a i ] k * ([A, a j , B] –[A]*b 1 * b 2 *…*b m * a j )] 因为[A, a j][A]* aj 1所以[A, a j, B] [A]*b1 * b2 *…*bm* a j //[ A aj B ] ( [ A ]*aj 1 )*B1 [ A ] * aj*B B 1 则必定有 [[A], a i ,{B}, a j ] [A, a j , {B}, a i ] ∴引理成立。 引理推广 [{A}, a i ,{B}, a j ] [{A}, a j , {B}, a i ] 当 [{A}]a i a j [{B}] A的任意顺序 引理[ [A] , ai, {B}, aj ] [ [A], aj, {B}, ai ]。 根据计算可以得出 [A , ai ] [ [A], ai ] 但是[ai,A] [ai,[A] ] 比如[ai ,a1,a2] (ai*a11)*a21 ai*a1*a2ai*a1a21 [ai,[A]]ai*(a1*a21)ai*a1*a2ai 【引理】 设有数列集合A和B,正整数a i , a j ,且有[A]a i a j [{B}] 其中B{b 1 , b 2 , …b m }{B}表示B中元素的任意组合序列则 有[[A], a i , {B}, a j ] [[A], a j , {B}, a i ]。 可以数字1~4为例根据引理必有 [[1, 2, 3], 4] [[1, 2, 4], 3] [[1, 3, 4], 2] [[2, 3, 4], 1] //两项同样适用 求证新加入一个元素 按照数列里最小值优先组合的规则仍可以得到最大值。 证前n个步骤得到数列A的第n阶段极大值[A n ] 依据 任意性可知加入一个新元素 按数列元素最小值优先组合的规则仍可以得到最大值。则kn1时命题成立 计算模型 (1)存储 用数组a[n]来数列 (2)计算 取最小值和第二小值 v min min{a[n]}, v mins min{{a[n]}-{v min }} 取最大值和第二大值 v max max{a[n]}, v maxs max{{a[n]}-{v max }} 极大值计算a[v min ]a[ v min ]*a[ v mins ]1 //这里vmin是下标 极小值计算a[v max ]a[v max ]*a[v maxs ]1 用最后一个元素覆盖a[ v mins ]或a[v max ] 代码 #includebits/stdc.h
using namespace std;
//堆排序 -完全二叉树
/*01 23 4 5 6
*/void show(int a[],int n)
{for(int i0;in;i){couta[i]\t;}coutendlendl;
}void min_h(int a[],int start,int end)
{//建立父节点指针和子节点指针int fstart;///父节点 int cf*21;//左孩子 int t;//用于交换的临时变量 while(cend)//若子节点指针在范围内进行比较 {//找到最小值的下标 if(c1end a[c]a[c1])//右孩子在范围中左孩子右孩子 {c;}//选中左右孩纸中较小值 //如果父节点 子节点 //此时 父右左 调整完成 if(a[f]a[c])return;else//交换 父右 左右 右是最小的 换到父节点上去 {ta[f];a[f]a[c];a[c]t;fc;cf*21;}}
}
void min(int a[],int n)
{//初始化 i从最后一个父节点开始调整for(int in/2-1;i0;i--){min_h(a,i,n-1);} for(int in-1;i0;i--){swap(a[0],a[i]);min_h(a,0,i-1);}
}
int cal(int a[], int n)
{int v10,v21;while (n 2){show(a,n);min(a, n);//maxa[v1] a[v1] * a[v2] 1;a[v2] a[n-1];//下次还需排序因此不用在意顺序直接将最后一个向前移动n n - 1;//数目--}//此时n2return a[0] * a[1] 1;
}
int main()
{int n 4;int a[4] { 8,2,1,3 };cout最大极差 cal(a, n);return 0;
}【例7-3】最优装载。 有一批集装箱准备装上轮船编号依次 为1, 2, …, n其中集装箱i的重量是w ii1, 2,…, n。已知轮船最 多装载量是C每个集装箱的重量w i≤C且对集装箱无体积限 制设计算法求如何选择能够使得装上的集装箱个数最多。 问题分析 贪心策略轻者优先 算法设计与描述 算法分析 输入1问题输入规模为n输出 2选择集装箱是主要工作时间渐进复杂度T(n)n 3排序最快的时间复杂度T(n)O(nlogn) 4上述23是并列执行的按照第2章的定理2.2可知时间渐进复杂度T(n)O(nlogn) t[]数组存放集装箱的原始编号。通过t 找到x 下标变量 【例7-4】键盘输入 键盘输入一个高精度的正整数N去掉其中任意 S个数字后剩下的数字按原左右次序将组成一个新的正整 数。对给于定的N和S寻找一种方案使得剩下的数字组成 的新数最小。 输出包括所去掉数字的位置和组成的新正整数 问题分析 (1) 高位的数字尽量小 (2) 删除策略贪心删除高位较大的数字相邻 两位比较若高位比低位大则删除高位。 (3) 枚举归纳如当s3时输入如下符串 n1“1 2 4 3 5 8 6 3” n2“2 3 1 1 8 3 1” n3“1 2 3 4 5 6 7” n4“1 2 0 0 8 3” 》 n1“1 2 3 5 3” n2“2 1 1 1” 应该是1131 需要回溯只需向上回溯一位 n3“1 2 3 4 5 6 7” 应该直接划掉后三个 没删除 有木有 n4“1 0 0 3” 没删够 有木有 (4) 物理删除覆盖已删除的字符字符串长度改变。 计算模型 (1)存储 a[]存储字数Ndata[]记录删除的元素在原 数字中位置存在一位回溯的操作设置变量j1来记 住上一次删除的位置。//因为删除本身位置就变了不记住无法找到位置 (2)计算 删除a[i]a[i1]nn-1。i为数列下标 记录删除位置 //i是几就删除几次 data[i]ji, j1j, if j≥j1 //不是回溯 data[i] data[i-1]-1, if jj1 //回溯位 其中i为删除次数j为数列下标 1.删除高位里的大值 2.回溯一位 3.末尾剩几个砍几个 4.高位0 代码 #includebits/stdc.h
using namespace std;int n 6;//长度
int s 3;//要删除的数字个数
char a[] { 1,2,0,0,8,3 };//数字
int data[3] { 0 };//记录删除的元素在原数字中的位置 void show(char a[])
{for(int i0;istrlen(a);i)couta[i]\t;coutendl;
}
void del(char a[], int b, int k)//删除,物理覆盖
{for (int i b; i strlen(a); i){a[i] a[i k];}
}
void delD(char a[], int s)
{int i 0, j 0, j1 -1;//存在回溯 int len strlen(a);//截止到\owhile (i s j strlen(a)){show(a);while (a[j] a[j 1])//一直是前面小 {j;}//前面大于后面if (j strlen(a)){//删除a[j]del(a, j, 1);//删除次数 i if (j j1)data[i] j i;//删除的第i个元素在原数组中的位置是ji else data[i] data[i - 1] - 1;//回溯回溯到上一个删除位置 的前一个位置 //j1 j;i;j--;if (j 0)j 0;}}//显示的时候高位的0不显示 while (a[0] 0 strlen(a)) del(a, 0, 1);}int main()
{delD(a, s);cout位置endl;for(int i0;is;i){coutdata[i]\t;}coutendl新整数;for (int i 0; i n-s; i)cout a[i];return 0;
} 近似贪心问题 局部最优 达不到 全局最优
