柚子快报邀请码778899分享：学习 贪心算法和动态规划
目录
思想：
a.贪心算法:
b.动态规划：
解题步骤：
a.贪心算法解题的基本步骤：
b.动态规划解题的基本步骤
经典例题：
1.分发饼干：
2.移除k个数字：
3.最小路径和
4.哈夫曼树
思想：
a.贪心算法:
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。
贪心算法的核心思想是在每一次对问题的分析上都寻求一个最优解，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是某种意义上的局部最优解。
b.动态规划：
动态规划算法通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
动态规划的核心思想是把原问题分解成子问题进行求解，也就是分治的思想。（大事化小，小事化了）
解题步骤：
a.贪心算法解题的基本步骤：
1.将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解
2.证明做出贪心选择后，原问题总是存在最优解，即贪心算法是安全的
3.证明做出贪心选择后，剩余的子问题满足性质：其最优解和贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。很明显，在每个贪心算法之下，几乎总有一个更繁琐的动态规划算法
b.动态规划解题的基本步骤
确定问题的状态：将问题划分成若干个子问题，然后确定每个子问题的状态。确定状态转移方程：找到子问题之间的关系，然后利用这些关系来建立状态转移方程。确定边界条件：确定问题的边界条件，即初始状态和终止状态。解决问题：根据状态转移方程和边界条件，求解问题的最优解。
以上为贪心算法和动态规划的基本思想和解题的基本步骤
经典例题：
1.分发饼干：
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
代码如下：
#include
#include
int comp(const void*a,const void*b)//用来做比较的函数。
{
return *(int*)a-*(int*)b;
}
int main(){
int n,m; //n为小孩人数 ，m 为饼干个数
scanf("%d%d",&n,&m);
int i,j;
int appetite[n+1]; //小孩的胃口值
for(i=1;i<=n;i++){ //小孩的序号从1开始
scanf("%d",&appetite[i]);
}
int biscuits[m+1]; //饼干大小
for(i=1;i<=n;i++){
scanf("%d",&biscuits[i]);
}
/* 我们的目标是要尽可能满足更多的孩子，所以我们的先要满足的孩子是那些胃口小的，
所以我们先对胃口值进行排序 */
qsort(appetite,n+1,sizeof(int),comp);
/* 同时对饼干大小进行排序 */
qsort(biscuits,m+1,sizeof(int),comp);
i=j=1;
while(i<=n&&j<=m){
if(appetite[i]<=biscuits[j]){
i++; /*只有当这个孩子能够被满足时，才考虑下一个孩子 ，
所以不需要另外定义一个变量来记录被满足孩子的个数 */
}
j++; /* 题目中要求一个孩子只能有一个饼干，因为我们已经对孩子胃口进行排序，
当这块饼干不能满足小孩时，上一块肯定也不能，所以直接看下一块更大的饼干即可 */
}
printf("%d",i-1); //由于时从第一个孩子还是，i的初始值为1 ，所以需要减一
return 0;
}
2.移除k个数字：
给你一个以字符串表示的非负整数num和一个整数k，移除这个数中的k个数字，使得剩下的最小，请你以字符串的形式返回这个最小的数字。
思路：
假定给出一个数 num =543219， k =3 ；显然被返回的最小的数字为 219；
在做这个题的时候，我们要想，应该删除哪k个数，为什么删掉他们，他们之间有什么规律。
首先要想让这个数最小，假设我们只是删除掉最大的数，那么我们得到的结果时321，显然这是错误的。
思考，当k=1时，我们删掉一个数，当最高位会大于次位时，将次位作为做高为肯定时最小的，即便最后一个数有多大也是如此，而如果最高位小于次位，那么我们继续寻找下一位会大于其次位的数，它就是我们需要删除的数。
这题，我们可以在找到这位时，使用循环将其移位，但当k很大时，每删除一次就需要移位一次，这样所耗费的时间将会很多，所以我们采取使用另外一个数组来接收这个删除了需要被删除后数组。
代码如下：
#include
#include
int main(){
char a[100];
char stack[100];
memset(a,'\0',sizeof(a));
memset(stack,'\0',sizeof(stack));
scanf("%s",&a);
int k=0;
int i,j;
int n=0;
scanf("%d",&k);
int length=strlen(a);
if(k while(n for(i=0;i if(a[i]>a[i+1]){ j=i+1; //找到这个要被删除的数 break; }else{ stack[i]=a[i]; } } for(;j stack[i++]=a[j]; } n++; memset(a,'\0',sizeof(a)); //将大小为sizeof(a)的内存全置为中间所给出的字符 strcpy(a,stack); //将stack copy 给 a memset(stack,'\0',sizeof(stack)); } printf("%s",a); }else{ printf("0"); } return 0; } 3.最小路径和 给定一个包含非负整数的m*n网格，请找出从左上角到右下角的路径，使得路径上的数字总和最小。每次只能向下或向右一步。 思路：这里我一开始的想法是用我之前写过的一篇文章里的方法，用三个变量来完成动态规划，但查询了一下别人的思路之后发现，使用一个二维数组更加方便，二维数组里的每一个元素的值代表的是从左上角到这个位置的最小路径，所以我们最后的结果就是我们二维数组最后一个元素的值。 这个方法我们需要考虑三种情况： 边界： 1.只有一行时：我们只能够向右移动，所以一直加到最后即可！ 2.只有一列时：我们只能向下移动，一直加到最后即可！ 正常情况：3.我们可以向右或者向下移动，这里我们重新创建了一个二维数组temp来表示左上方到现在位置的距离，这里我想了两种思路： 1.假设我们现在在temp[i][j],此时我们向右走则temp[i][j+1]=temp[i][j]+a[i][j+1],若我们向下走则temp[i+1][j]=temp[i][j]+a[i+1][j] 2.假设我们下一步要到temp[i][j],那么此时我们可能在temp[i-1][j]或者temp[i][j-1],temp[i][j]=temp[i-1][j]+a[i][j]或者temp[i][j]=temp[i][j-1]+a[i][j] 第一种更比较倾向于贪心算法，但仔细思考了之后我发现这样是不行的，每一次选择了一个最小值，但得到的结果却不一定是最小的，举个例子{(1,2,1),(1,2,1),(1,5,1)}这里如果采用第一种每一次走最小值，走到最后我们可能会走到一个很大的数，但我们只能走向这里，就会产生问题。 第二种，我认为它更像从结果反推到前面，这里我们也可以用递归来算。 第二种方法的代码实现： #include #include int a[100][100] ; int min(int k,int t){ if(k>t){ return t; }else{ return k; } } int across(int a[][100],int m,int n){ int temp[m][n]; //temp[][] 中元素表示 从a[0][0] 到 a[i][j] 的长度大小，所以最后我们的结果就是 temp[m-1][n-1] temp[0][0]=a[0][0]; if(m==0&&n>0){ for(int i=1;i temp[m][i]=a[m][i]+temp[m][i-1]; } } else if(n==0&&m>0){ for(int i=1;i temp[i][n]=temp[i-1][n]+a[i][n]; } } else{ for(int i=1;i for(int j=1;j temp[i][j]=min(temp[i-1][j],temp[i][j-1])+a[i][j]; } } } return temp[m-1][n-1]; } int sum=0; int main(){ int m,n; scanf("%d%d",&m,&n); //m 作为行，n 作为列 for(int i=0;i for(int j=0;j scanf("%d",&a[i][j]); } } printf("%d",across(a,m,n)); return 0; } 4.哈夫曼树 这是我上课的时候在课堂上的一个思路，虽然我的思路是错的，嘿嘿，但我觉得这也是我的问题不清楚，不知道什么时候可以用贪心。 哈夫曼树的构建要求树的带权路径长度最短 我先说我自己的思路吧：我当时看到这个就想着我只要让权值最大的那个节点在最上方依次向下就能得到哈夫曼树。 设置权值A>B>C 但这样是有问题的！！！ 接下来看一下正确的方法吧，我们每次寻找两个权值最小的节点，将他们类似于地基一样一层一层向上叠加。 代码实现如下： #include #include typedef struct { int weight; int parent,lchild,rchild; }HTree; int comp(const void*a,const void*b)//用来做比较的函数。 { return *(int*)a-*(int*)b; } void createNode(HTree *p,int n); int main(){ int n; //代表哈夫曼树中带权值的 n 个节点 printf("请输入哈夫曼树中带权值的节点数：\n"); scanf("%d",&n); HTree *p; createNode(p,n); return 0; } void createNode(HTree *p,int n){ if(n<=1){ //只有一个节点就没必要构成树了 return; } int m=2*n-1; //由图可以清晰看到 ，当带权值节点个数为 n 时 ，我们一共需要 2*n-1 个节点 p=(HTree *)malloc((m+1)*sizeof(HTree)); //为了方便，我们从 1 开始 for(int i=1;i<=m;i++){ //将 m 个节点的父节点，左孩子节点，右孩子节点都置为0 p[i].parent=0; p[i].lchild=0; p[i].rchild=0; } printf("请输入各个节点的权值：\n"); for(int i=1;i<=n;i++){ scanf("%d",&p[i].weight); //将前 n 个节点赋予权值 } for(int i=n+1;i<=m;i++){ int min1 = 65535; int Fnode = -1; //作为最小的节点的下标 int min2 = 65535; int Snode = -1; //最为第二小节点的下标 for (int j = 1; j <= i - 1; j++) //这里就是在寻找最小的权值和第二小的权值了 { if (p[j].weight < min1 && p[j].parent == 0) //这里写==0是因为确保已经找到过的最小和第二小两个节点不会被再一次选择 { min2 = min1; Snode = Fnode; min1 = p[j].weight; Fnode = j; } else if (p[j].weight < min2 && p[j].parent == 0) { min2 = p[j].weight; Snode = j; } } p[Fnode].parent = p[Snode].parent = i; p[i].lchild = Fnode; p[i].rchild = Snode; p[i].weight = p[Fnode].weight + p[Snode].weight; } } 该篇小分享就到这里为止了，虽然我好像还不是很懂，在我想用贪心的时候很多时候都发现贪心好像并不能得到结果，还是得动态递归，emmm....希望有懂的大哥给出意见，在这里说声谢谢了! 柚子快报邀请码778899分享：学习 贪心算法和动态规划 精彩内容
发表评论