vlambda博客
学习文章列表

一、贪心算法

    也称贪婪算法。

    它在求解问题时，总想用当前看来最好的方法来实现。

    这种算法思想不从整体最优上考虑问题，仅是在某种意义上求解局部最优解。

    虽然贪心算法并不能得到所有问题的整体最优，但是面对范围相当广的许多问题时，它能产生整体最优解或者整体最优解的近似解。

    由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。

    （感觉说了跟没说一样，或许是第一印象的算法解吧？！）

二、贪心算法的基础

    贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。

    当达到算法中的某一步不能再继续前进时，就停止运行，并给出一个近似解。

    由贪心算法的特点和思路可看出，贪心算法存在以下3个问题。

        1）不能保证最后的解是最优的。

        2）不能用来求最大或最小解的问题。

        3）只能求解满足某些约束条件的可行解范围。

    贪心算法的基本思路如下所示。

        1）建立数学模型来描述问题。

        2）把求解的问题分成若干个子问题。

        3）求解每一子问题，得到子问题的局部最优解。

        4）把子问题的局部最优解合并成原来问题的一个解。

    实现该算法的基本过程如下所示。

        1）从问题的某一初始解出发。

        2）while语句能向给定总目标前进一步。

        3）求出可行解的一个解元素。

        4）由所有解元素组合问题的一个可行解。

三、实战演练——装箱

    使用贪心算法解决“装箱”问题。

    问题描述：

        假设有编号分别为0，1，……，n-1的n种物品，体积分别为V0，V1……Vn-1。

        将这n种问题装到容量都为V的若干个箱子里。

        约定n种物品的体积均不超过V，即对于0<=i<n时，有0<Vi<V。

    算法分析：

        如果将n种物品分解为n个或小于n个物品的子集，那么使用最优解法就可以找到答案。

        但是对于所有可能的划分，总数会显得太大。

        对于适当大的n，如果要找出所有可能的划分，则需要花费很多时间。

        此时可以使用贪心算法这种近似算法来解决装箱问题。

        如果每只箱子所装物品都用链表来表示，则链表的首节点指针保存在一个结构中，该结构能够记录剩余的空间量和该箱所装物品链表的首指针，然后使用全部箱子的信息构成链表。

    代码实现：

# include<stdio.h>#include<stdlib.h>
#define N 6#define V 100typedef struct box { int no; int size; struct box* next;}BOX;
void init_list(BOX** H) { *H = (BOX*)malloc(sizeof(BOX)); (*H)->no = 0; (*H)->size = 0; (*H)->next = NULL;}
BOX* find_p(BOX* H, int volume, int v) { BOX* p = H->next; while (p!=NULL) { if (p->size + volume <= v) { break; } p = p->next; } return p;}
void add_list_tail(BOX* H, BOX* p) { BOX* tmp = H->next; BOX* q = H; while (tmp!=NULL) { q = tmp; tmp = tmp->next; } q->next = p;}
void print_list(BOX* H) { BOX* p = H->next; while (p != NULL) { printf("%d:%d\n", p->no, p->size); p = p->next; }}
int add_box(int volume[], int v) { int count = 0; int i; BOX* H = NULL; init_list(&H); for (i = 0; i < N; i++) { BOX* p = find_p(H, volume[i], v); if (p == NULL) { count++; p = (BOX*)malloc(sizeof(BOX)); p->no = count; p->size = volume[i]; p->next = NULL; add_list_tail(H, p); } else { p->size += volume[i]; } } print_list(H); return count;}
int main(){ int ret; int volumes[] = { 60,45,35,20,20,20 }; ret = add_box(volumes, V); printf("%d\n", ret); }

    分析：

        首先是定义两个变量，N个物品，容量V的箱子。

        然后是创建一个打印链表的函数，将其中的变量no和变量size打印出来。

        然后是创建一个添加盒子的变量，参数是一个数组和一个int类型的v。

        然后通过for循环，对每一种物品进行筛选操作。

            如果指针p为NULL，则执行下面的代码：

                首先是对count变量进行+1计数；

                再往单链链表的尾部进行添加。

            如果指针p不为NULL，则直接将当前内存空间中的size变量累加一个volume[i]的数值。

        最后是打印整个链表，并返回一个计数变量count。

        然后就是在main函数中执行。

            首先定义了一个返回count计数变量ret；

            然后又定义了一个数组volume[]，应该是每个箱子的尺寸。而数组的长度，需要跟前面定义的常量N一致。

            然后就是执行添加箱子的函数，即add_box()，参数是volume[]和前面定义的常量V，箱子的尺寸。

            而该函数会直接打印符合要求的单链中的内容，并且返回的计数count的值，也赋值给定义的ret变量。

    运行结果：

PS：

    说实话，想必是自己对单链还是理解的不错，所以在还没有完全明白变量no、size、N、V和volume的情况下，先了解了前面是先定义了一个struct box的数据类型，以及以这个数据类型开辟内存空间，并构成单链的相关操作函数。

    而add_box()函数，才是将其综合起来的主要函数。

    至于在main函数中，只是单纯的调用这个函数而已。

    而本该循环6次，却只输出3次，其实是60+45<100，35+20+20<100，20<100这三次。

    也就是说，这个函数的功能是，往一个容量为100的箱子里装数，如果累加起来不超过100，就一直使用同一个箱子，直到超过100后，就再新创建个箱子往里面装。

    （感觉这就是典型的往512个字节为一个单位的硬盘空间中的典型案例啊！）

    虽然过了一遍，但我可能肯定的是，自己并没有完全理解。

    同时也不由的自我吐槽一下，我明明手打的一般题目，可最终却根本就没有去理解题意，反而是通过捋顺答案去验证题目，这毛病可不好，会造成没有答案就不能干活，可有了答案又没必要干活的尴尬处境。

    还有就是自己的抽象能力，也需要加强。也就是把代码抽象化的能力，虽然也是代码，可要是拥有这项能力后，那么“代码”将不再是“代码”，会构成一种特殊的感觉？像是将复杂海量的文字，一下子就压缩成一张图片可直观理解的感觉？！