算法系列：贪心算法
<div id="cnblogs_post_body">贪婪算法的基本思想：通过一系列步骤来构造问题的解，每一步都是对已构造的部分解的一个扩展，直到获得问题的完整解。贪婪算法中，每一步&ldquo;贪婪地&rdquo; 选择最好的部分解，但不顾及这样选择对整体的影响（局部最优），因此得到的全局解不一定最好的解，但对许多问题它能产生整体最优解。
具体算法描述：
<div id="codeSnippetWrapper"><div id="codeSnippet" style="text-align: left; line-height: 12pt; background-color: #f4f4f4; width: 100%; font-family: 'Courier New', courier, monospace; direction: ltr; color: black; font-size: 8pt; overflow: visible; border-style: none; padding: 0px;"> 1: void Knapsack(int n,float M, float v[], float w[], float x[]) 2: { 3: Sort(n, v, w); 4: int i; 5: for(i = 1; i < n; i++) 6: x = 0; 7: float c = M; 8: for(i = 1; i < n; i++) 9: {10: if(w > c)11: break;12: x = 1;13: c -= w;14: }15: if(i <=n)16: x = c/w;17:
页:
[1]