表示一个算法常用的方法有分治法、动态规划、贪心法和回溯法。
一、分治法
定义：分治法是一种将问题分解成若干个子问题然后逐个解决的方法。每个子问题的解合并起来，最终得到原问题的解。步骤：分解：将原问题分解为若干个规模较小的子问题。解决：递归地求解各个子问题。合并：将各个子问题的解合并成原问题的解。
二、动态规划
定义：动态规划是通过将问题分解为相互重叠的子问题来求解的一种方法。它保存子问题的解，避免重复计算，以提高效率。
步骤：确定状态：确定问题可以通过哪些状态来描述。定义状态转移方程：找到问题的递推关系，即当前状态与之前某些状态之间的关系。确定边界条件：确定初始状态的值或边界情况下的解。计算顺序：按照一定的顺序计算各个子问题的解。
三、贪心法
定义：贪心法是一种通过每一步选择当前最优解，以期望获得全局最优解的方法。它不考虑未来的情况，只关注眼前能够得到的最优解。
步骤：选择贪心策略：根据问题的特性和约束条件，选择每一步的最优解。判断可行性：验证所选择的最优解是否满足问题的约束条件。更新解空间：更新问题的解空间，继续进行下一步的选择。
四、回溯法
定义：回溯法是一种通过尝试所有可能的解，并在搜索过程中剪枝来求解问题的方法。它适用于各种组合、排列、子集等类型的问题。步骤：选择路径：从初始状态开始，选择一个合适的路径，进入下一层状态。探索路径：在当前状态下，沿着路径向前探索并搜索所有可能的解。
结果判断：判断当前路径是否为有效解，如果是则记录，如果不是则返回上一层状态并继续探索其他路径。剪枝操作：根据问题的特点，在搜索过程中剪除不符合要求的路径，减少搜索空间。
拓展知识：
分治法：在排序算法（如归并排序和快速排序）中常用分治法来提高效率，也广泛应用于各种图形处理问题。动态规划：动态规划算法被广泛应用于最短路径问题、背包问题、序列比对等领域。贪心法：贪心法常用于任务调度、图的遍历、集合覆盖等问题。回溯法：回溯法常用于搜索问题，如八皇后问题、数独等。
回溯法是一种选优搜索法（试探法）。
基本思想：将问题P的状态空间E表示成一棵高为n的带全有序树T，把求解问题简化为搜索树T。搜索过程采用 深度优先搜索 。搜索到某一结点时判断该结点是否包含原问题的解，如果包含则继续往下搜索，如果不包含则向祖先回溯。
通俗来说，就是利用一个树结构来表示解空间,然后从树的根开始深度优先遍历该树，到不满足要求的叶子结点时向上回溯继续遍历。
几个结点：
扩展结点：一个正在产生子结点的结点称为扩展结点
活结点：一个自身已生成但未全部生成子结点的结点
死结点：一个所有子结点已全部生成的结点
1、分析问题，定义问题解空间。
2、根据解空间，确定解空间结构，得 搜索树 。
3、从根节点开始深度优先搜索解空间（利用 剪枝 避免无效搜索）。
4、递归搜索，直到找到所要求的的解。
1、子集树
当问题是：从n个元素的集合S中找出满足某种性质的子集时，用子集树。
子集树必然是一个二叉树。常见问题：0/1背包问题、装载问题。
遍历子集树时间复杂度：O（2^n）
2、排列树
当问题是：确定n个元素满足某种排列时，用排列数。常见问题：TSP旅行商问题，N皇后问题。
遍历排列树时间复杂度：O（n!）
通俗地讲，结合Java集合的概念，选择哪种树其实就是看最后所得结果是放入一个List（有序）里，还是放入一个Set（无序）里。
剪枝函数能极大提高搜索效率，遍历解空间树时，对于不满足条件的分支进行剪枝，因为这些分支一定不会在最后所求解中。
常见剪枝函数：
约束函数（对解加入约束条件）、限界函数（对解进行上界或下界的限定）
满足约束函数的解才是可行解。
1、0/1背包问题
2、TSP旅行商问题
3、最优装载问题
4、N-皇后问题
具体问题可百度详细内容。
问题一：贪心算法的例题分析例题1、[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品 A B C D E F G重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg价值 10$ 40$ 30$ 50$ 35$ 40$ 30$分析：目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi 64输出一个解，返回上一步骤c--（x,y) ← c计算(x,y）的八个方位的子结点，选出那些可行的子结点循环遍历所有可行子结点，步骤c++重复2显然⑵是一个递归调用的过程，大致如下：C++程序： #define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(count>N*N) { output_solution();输出一个解 return; } for(i=0; i>
问题二：收集各类贪心算法（C语言编程）经典题目tieba.baidu/...&tb=on百度的C语言贴吧。 全都是关于C的东西。
问题三：几种经典算法回顾今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。
2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | >
问题四：求三四个贪心算法的例题（配源程序代码，要带说明解释的）！非常感谢贪心算法的名词解释
baike.baidu/view/298415
第一个贪心算法 （最小生成树）
baike.baidu/view/288214
第二个贪心算法 （Prim算法）
baike.baidu/view/671819
第三个贪心算法 （kruskal算法）
baike.baidu/view/247951
算法都有详细解释的
问题五：求 Java 一些经典例子算法前n项阶乘分之一的和
public class jiecheng {
public static void main(String[] args)
{
double sum=0;
double j=1;
int n=10;
for(int i=1;i问题六：关于编程的贪心法定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi>
问题七：求解一贪心算法问题最快回答那个不懂别乱说，别误人子弟。
这题标准的贪心算法，甚至很多时候被当做贪心例题
要求平均等待时间，那么就得用 总等待时间 / 人数
所以只用关心总等待时间，
如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。
给你写了个，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i > arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i问题八：分治算法的应用实例下面通过实例加以说明： 给你一个装有1 6个硬币的袋子。
1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下：void maxmin1(int A[],int n,int *max,int *min){ int i;*min=*max=A[0];for(i=0;i *max) *max= A[i];if(A[i] >
问题九：回溯算法的典型例题八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
问题十：什么是算法，都什么，举个例子，谢谢算法就是解决问题的具体的方法和步骤，所以具有以下性质：
1、有穷性： 一个算法必须保证执行有限步之后结束（如果步骤无限，问题就无法解决）
2、确切性：步骤必须明确，说清楚做什么。
3、输入：即解决问题前我们所掌握的条件。
4、输出：输出即我们需要得到的答案。
5、可行性：逻辑不能错误，步骤必须有限，必须得到结果。
算法通俗的讲：就是解决问题的方法和步骤。在计算机发明之前便已经存在。只不过在计算机发明后，其应用变得更为广泛。通过简单的算法，利用电脑的计算速度，可以让问题变得简单。
NOIP级别中，普及组和提高组的要求不同。
但是这几类动规的题目掌握了，基本也就可以了：
1、背包问题：01背包、完全背包、需要构造的多维01背包
详见背包九讲
2、最大降序：例如打导弹
3、矩阵相乘：例如能量珠子
4、买股票
5、方格取数：单向的、双向的
6、三角取数
这些都是简单的动规的应用，必须掌握，背也要背出来，还要会套用。
至于排序，本人认为基本的选择排序大家都会，快速排序是一定要会的，当数据规模<500时用选择排序，当数据规模在500和100000之间是用快速排序，但是NOIP中经常考到基数排序，例如划分数线等，数据规模会达到1000000，用其他的排序法可能会超时一两个测试点。
至于搜索，那是必须掌握的深搜、广搜都要会，主要是深搜，当提高组碰到一下子想不出动规的状态转移方程式，深搜穷举也是可行的，一般都能拿到不少的分数。个人之间广搜的用处不大，程序复杂而且爆机率很高。当然n个for的穷举法在不得已的时候也能得不少分，只要if剪枝的好，对付八后问题等问题时，时间效率比很高。
另外就是图的遍历，有关图的最小生成树、图的单源最短路径，也是需要很好地掌握，一直会考。当然，深搜的本事高的人可以用深搜搞定。
总结如下：要得一等，必须对模拟法和穷举法有深刻的体会，并知道很多变通的手段；对快排要背的滚瓜烂熟；对深搜要做到不管是贪心还是动规的题，都能用深搜实现，只不过少量点超时而已；动规要记住六大模型，然后背包要理解透彻；数学很重要，数学分析的题要做对，例如排组合、凸包、计算几何近几年常考。有了这些，一等可以稳拿。
与回溯法一样，分支限界法也是在问题的解空间树上搜索问题的解的一种算法。
两者很类似，很容易混淆，但有如下显著的区别可区分两者：
1、求解目标不同
回溯法的求解目标一般是找出解空间树中满足条件的 所有解 。
分支限界法则是尽快找出满足约束条件的 一个解 ，或是在满足约束条件的解中找出在某种意义下的 最优解 。
2、搜索方式不同
回溯法——> 深度优先遍历结点搜索解空间树。
分支限界法——> 广度优先或最小耗费优先 搜索解空间树。
3、存储空间不同
分支限界法由于加入了 活结点表 ，所以存储空间比回溯法大得多。因此当内存容量有限时，回溯法的成功率要大一些。
4、扩展结点的方式不同
分支限界法中，每个活结点只有一次机会变成扩展结点，一旦成为扩展结点便一次性生成其所有子结点。
区别小结：回溯法空间效率更高，分支限界法由于只需要求到一个解，所以往往更“快”。
就拿0/1背包问题做例子，回溯法求解0/1背包问题实际上是盲目地搜索解空间树，回溯法只会不断地往下走，虽然通过剪枝函数能减少一定的计算，但是当经过一个结点时，并不知晓其子结点会是怎样的情况，从而盲目继续搜索。而分支限界法则不一样，在经过某一结点时，会根据限界条件判断其结点之下的情况是否能够导出最优解，如若不能，直接不走这条路。这样虽然在空间上不占优势，但是搜索并不盲目，速度上快了很多。
1、定义解空间（对解编码）
2、确定解空间树结构（得解空间树）
3、按BFS广度优先方式搜索解空间树：
（1）：每个活结点只有一次机会变成扩展结点。
（2）：由扩展结点生成一步可达的新结点。
（3）：在新结点中删除不可能导出最优解的结点（限界策略，利用限界函数）。
（4）：将剩余新结点加入到活结点表中。
（5）：在活结点表中再取每个结点（按顺序）进行扩展（分支策略）。
（6）：直到活结点表为空。
注：活结点表通常采用堆结构，当求解极大值问题时用大顶堆，极小值问题时用小顶堆。
1、约束函数：问题定义时需给出的约束条件，如0/1背包问题不能超过其容量。
2、目标函数：是问题要求解的目标函数，分支限界法中需给出一个关于该函数的上下界，方便之后剪枝。
3、限界函数：用于记录当前结点之下可得的最优值，若超出上下界，则可放弃该结点；还用于活结点表中结点排序，限界函数值最优的在第一位，优先扩展遍历。
1、队列式分支限界法：在活结点表中，按照FIFO先进先出原则选取下一个结点做扩展结点。
2、优先队列式分支限界法：活结点表中的每个结点对应了一个耗费或收益（其实就是如果扩展该结点，会带来多大的效益），以此决定结点的优先级。
0/1背包问题、单源最短路径问题、最优装载问题。
对于一名优秀的程序员来说，面对一个项目的需求的时候，一定会在脑海里浮现出最适合解决这个问题的方法是什么，选对了算法，就会起到事半功倍的效果，反之，则可能会使程序运行效率低下，还容易出bug。因此，熟悉掌握常用的算法，是对于一个优秀程序员最基本的要求。
那么，常用的算法都有哪些呢？一般来讲，在我们日常工作中涉及到的算法，通常分为以下几个类型：分治、贪心、迭代、枚举、回溯、动态规划。下面我们来一一介绍这几种算法。
一、分治算法
分治算法，顾名思义，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治算法一般分为三个部分：分解问题、解决问题、合并解。
分治算法适用于那些问题的规模缩小到一定程度就可以解决、并且各子问题之间相互独立，求出来的解可以合并为该问题的解的情况。
典型例子比如求解一个无序数组中的最大值，即可以采用分治算法，示例如下：
def pidAndConquer(arr,leftIndex,rightIndex):
if(rightIndex==leftIndex+1 || rightIndex==leftIndex){
return Math.max(arr[leftIndex],arr[rightIndex]);
}
int mid=(leftIndex+rightIndex)/2;
int leftMax=pidAndConquer(arr,leftIndex,mid);
int rightMax=pidAndConquer(arr,mid,rightIndex);
return Math.max(leftMax,rightMax);
二、贪心算法
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法的基本思路是把问题分成若干个子问题，然后对每个子问题求解，得到子问题的局部最优解，最后再把子问题的最优解合并成原问题的一个解。这里要注意一点就是贪心算法得到的不一定是全局最优解。这一缺陷导致了贪心算法的适用范围较少，更大的用途在于平衡算法效率和最终结果应用，类似于：反正就走这么多步，肯定给你一个值，至于是不是最优的，那我就管不了了。就好像去菜市场买几样菜，可以经过反复比价之后再买，或者是看到有卖的不管三七二十一先买了，总之最终结果是菜能买回来，但搞不好多花了几块钱。
典型例子比如部分背包问题：有n个物体，第i个物体的重量为Wi，价值为Vi，在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。
贪心策略就是，每次都先拿性价比高的，判断不超过C。
三、迭代算法
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。最终得到问题的结果。
迭代算法适用于那些每步输入参数变量一定，前值可以作为下一步输入参数的问题。
典型例子比如说，用迭代算法计算斐波那契数列。
四、枚举算法
枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确地解。
枚举算法适用于候选答案数量一定的情况。
典型例子包括鸡钱问题，有公鸡5，母鸡3，三小鸡1，求m钱n鸡的所有可能解。可以采用一个三重循环将所有情况枚举出来。代码如下：
五、回溯算法
回溯算法是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
典型例子是8皇后算法。在8 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。
回溯法是求解皇后问题最经典的方法。算法的思想在于如果一个皇后选定了位置，那么下一个皇后的位置便被限制住了，下一个皇后需要一直找直到找到安全位置，如果没有找到，那么便要回溯到上一个皇后，那么上一个皇后的位置就要改变，这样一直递归直到所有的情况都被举出。
六、动态规划算法
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
动态规划算法适用于当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响，即无后效性的问题。
典型例子比如说背包问题，给定背包容量及物品重量和价值，要求背包装的物品价值最大。
#include
using namespace std;
struct bag{
double w;
double p;
double p_w;
int order;
}; //说明物品特性
void sort(struct bag *a,int low,int high);
int main()
{
int n,i;
double *x; //解向量，由于书数组，拿指针表示
double m,cost=0;
struct bag *b;//结构数组，用于表示所有物品
//定义文件流并与具体的磁盘文件相关联
ifstream fin;
fin.open("背包问题_in.txt");
ofstream fout;
fout.open("背包问题_out.txt");
//输入物品数目 n 背包容量 M
fin>>n>>m;
//动态分配存储空间
b=new struct bag[n];
x=new double[n];
for(i=0;i fin>>b[i].w>>b[i].p;//输入物品重量和运价 b[i].p_w=b[i].p/b[i].w; //求出运价重量比 b[i].order=i; //贴标签 } sort(b,0,n-1); //按运价重量比从大到小进行排序 for(i=0;i x[i]=0;//初始化解向量 for(i=0;i if(b[i].w<=m){ //若背包能放得下整个物品 x[b[i].order]=1; //放入背包 m-=b[i].w; //背包剩余容量减小 cost+=b[i].p;//总价值增加 } else{//否则，放不下整个物品 x[b[i].order]=m/b[i].w; //放一部分 cost+=x[b[i].order]*b[i].p;//总价值增加 break; //打断，后续物品由于不能放入背包，不需处理 } for(i=0;i fout< fout< //删除动态分配下的空间 delete []x; delete []b; //关闭文件指针 fin.close(); fout.close(); return 0; } int par(struct bag *a,int low,int high) { struct bag temp; temp=a[low]; double t; t=a[low].p_w; while(low while(low --high; a[low]=a[high]; while(low ++low; a[high]=a[low]; } a[low]=temp; return low; } void sort(struct bag *a,int low,int high) { int loc; if(low loc=par(a,low,high); sort(a,low,loc-1); sort(a,loc+1,high); } }
大家在关注
