贪婪法
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。
贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
贪婪算法的一般方法
1、问题描述
它有n个输入，而它的解就由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。
2、约束条件 那些必须满足的条件称为约束条件。
3、可行解 满足约束条件的子集称为该问题的可行解。
4、目标函数 事先给定的衡量可行解优劣的量度标准，通常以函数的形式给出，称为目标函数。
5、最优解 使目标函数取极值（极大或极小）的可行解，称为最优解。
6、子结构模式 贪心技术中，问题的最优一般是原输入的子集，获取最优子集的贪心方法为子结构模式
7、有序模式 通过计算已有的判定而得出的最优条件，可以为下一步的判定提供依据，这种形式的贪心算法称为有序模式。
8、贪婪算法求解思想（分步处理）
? 根据题意，选取一种量度标准；
? 然后按这种量度标准对这n个输入排序，并按序一次输入一个量。
? 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。
这种能够得到某种意义下的最优解的分级处理方法称为贪心算法。
背包问题贪婪法
题目大概意思：
比如说一堆食物。他们有重量。有热量。现在你可以任意选来吃。可以吃一个。可以吃半个。或者是1/3 。但是如何吃能得到物品的最大热量呢。以下程序就是解决这个问题的。
思想大概这样：热量大的未必能得到最大。因为你肚子有限吧。假如食物重量1公斤。放出的是5000。现在有一个0.3公斤。放出3000热量。在热量上来说是1公斤的事物多。但是他也重。这个时候要想得最大热量。就要求出每种食物的热量与重量之比。比值越大。代表效率越高。然后按照将序排列。得到食物热量与重量比值大的。小弟表达能力差。只能这样简单的说一下了。
#include<stdio.h>
main()
{
float v[]={25,24,15};/*物品价值*/
float w[]={18,15,10};/*物品重量*/
float Ratio[100],temp,temp_v,temp_w,tw,max=0.0;/*Ratio[]是求价值与重量的比值
temp_v累加物品价值
temp_w累加物品重量
max是求得的物品最大价值
tw表示背包的所能承受的最大重量*/
int i,j,k;
float biao[10];/*这个物品所取的重量之比,1表示全取.0.5表示取二分之一*/
for(k=0;k<10;k++)
biao[k]=0;
printf("请输入背包的最大容量:tw\n");
scanf("%f",&tw);
for(i=0;i<3;i++)
Ratio[i]=(v[i]/w[i]);
for(i=0;i<2;i++)/*按照比值将物品价值和重量降序排列*/
{
temp=Ratio[i+1];
temp_v=v[i+1];
temp_w=w[i+1];
j=i;
while(j>-1&&temp>Ratio[j])
{
Ratio[j+1]=Ratio[j];
v[j+1]=v[j];
w[j+1]=w[j];
j--;
}
Ratio[j+1]=temp;
v[j+1]=temp_v;
w[j+1]=temp_w;
}
i=0;
k=0;
while(tw>0)/*开始取物品.如果能装的一个就全装*/
{
if(tw>w[i])/*全装情况*/
{
tw=tw-w[i];
max=max+v[i];
biao[k++]=1;
i++;
}
else if(tw>0&&tw<=w[i])/*只能装1/n的情况*/
{
max=max+((tw/w[i])*v[i]);
biao[k++]=tw/w[i];
tw=0;
i++;
}
}
for(k=0;k<10;k++)/*以下是输出*/
if(biao[k]!=0)
printf("%f\t",biao[k]);
printf("\n");
printf("物品的重量是:\n");
for(k=0;k<10;k++)
if(biao[k]!=0)
printf("%f\t",w[k]);
printf("\n");
printf("所取的物品重量是:\n");
for(k=0;k<10;k++)
if(biao[k]!=0)
printf("%f\t",biao[k]*w[k]);
printf("\n");
printf("背包所取的重量是:%f\n",max);
}
分治法
点击数：1461 发布日期：2007-3-20 10:37:00
【收藏】 【评论】 【打印】 【编程爱好者论坛】 【关闭】
标签:代码
/* 分治法简介
任何一个可以用计算机求解的问题所需的计算时间都与其规模
有关。问题的规模越小，越容易直接求解，解题所需的计算时间也
越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。
n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。
而当n较大时，问题就不那么容易处理了。要想直接解决一个规模
较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一
些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决
（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的
子问题，这些子问题互相独立且与原问题形式相同，递归地解这些
子问题，然后将各子问题的解合并得到原问题的解。这种算法设计
策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解
并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行
的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递
归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问
题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容
易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪
生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子
结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公
共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复
杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提
它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特
征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具
备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或
动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的
则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用
分治法，但一般用动态规划法较好。
分治法的基本步骤
分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的
子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
6. T ← MERGE(y1,y2,...,yk) △ 合并子问题
7. return(T)
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问
题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，
用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)
求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问
题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。
根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？
各个子问题的规模应该怎样才为适当？
答: 但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模
大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之
有效的。许多问题可以取 k = 2。这种使子问题规模大致相等的做法是出自一
种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。
出处：网络
实践题目：
给定一个顺序表，编写一个求出其最大值和最小值的分治算法。
分析：
由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组
数组大小由用户定义，数据随机生成。我们知道如果数组大小为 1 则可以
直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解
该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了，只要
求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解
以下是代码。
*/
/*** 编译环境TC ***/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define M 40
/* 分治法获取最优解 */
void PartionGet(int s,int e,int *meter,int *max,int *min){
/* 参数:
* s 当前分治段的开始下标
* e 当前分治段的结束下标
* meter 表的地址
* max 存储当前搜索到的最大值
* min 存储当前搜索到的最小值
*/
int i;
if(e-s <= 1){ /* 获取局部解，并更新全局解 */
if(meter[s] > meter[e]){
if(meter[s] > *max)
*max = meter[s];
if(meter[e] < *min)
*min = meter[e];
}
else{
if(meter[e] > *max)
*max = meter[s];
if(met
