贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
下面我就拿两个例子大家一起来学学贪婪算法,我自己也是先看什么Dijkstra看不懂,从简单的开始吧...
【问题】 装箱问题
问题描述：装箱问题可简述如下：设有编号为0、1、…、n-1的n种物品，体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0≤i＜n，有0＜vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。
若考察将n种物品的集合分划成n个或小于n个物品的所有子集，最优解就可以找到。但所有可能划分的总数太大。对适当大的n，找出所有可能的划分要花费的时间是无法承受的。为此，对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。不失一般性，设n件物品的体积是按从大到小排好序的，即有v0≥v1≥…≥vn-1。如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。
这个就是一个典型的贪婪算法的问题,先取体积最大的
{ 输入箱子的容积；
输入物品种数n；
按体积从大到小顺序，输入各物品的体积；
预置已用箱子链为空；
预置已用箱子计数器box_count为0；
for (i=0;i { 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j；
if （已用箱子都不能再放物品i）
{ 另用一个箱子，并将物品i放入该箱子；
box_count++；
}
else
将物品i放入箱子j；
}
}
上述算法能求出需要的箱子数box_count，并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解，设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需三只箱子，各箱子所装物品分别为：第一只箱子装物品1、3；第二只箱子装物品2、4、5；第三只箱子装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。
若每只箱子所装物品用链表来表示，链表首结点指针存于一个结构中，结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。
|
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define V 100
typedef 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 argc, char *argv[])
{
int ret;
int volumes[] = {60, 45, 35, 20, 20, 20};
ret = add_box(volumes, V);
printf("%d\n", ret);
system("PAUSE");
return 0;
}
|
昨天刚看了背包问题,动态规划法,今天就用贪婪算法解解这个问题:这里是按性价比大小依次放入,先放性价比最大的...
|
#include <stdio.h>
#include <stdlib.h>
#define TOTAL_V 10
#define N 3
typedef struct object
{
float weight;
float value;
float ratio;//性价比
}OBJECT;
void swap(OBJECT* a, OBJECT* b)
{
OBJECT tmp = *a;
*a = *b;
*b = tmp;
}
int partition(OBJECT object[], int start, int end)
{
float x = object[end].ratio;
int i = start-1;
int j = start;
for(j=start; j<end;j++)
{
if(object[j].ratio-x>0.0001)
{
i++;
swap(&object[i], &object[j]);
}
}
swap(&object[i+1], &object[end]);
return i+1;
}
void sort(OBJECT object[], int start, int end)
{
if(start<end)
{
int q = partition(object, start, end);
sort(object, start, q-1);
sort(object, q+1, end);
}
}
void print_object(OBJECT object[], int n)
{
int i;
for(i=0;i<n;i++)
{
printf("weight:%f value:%f ratio:%f\n", object[i].weight,
object[i].value, object[i].ratio);
}
}
int greed(OBJECT object[], int n,int total)
{
int i;
int p =0;
int m = total;
for(i=0;i<n;i++)
{
if(object[i].weight<m)
{
p += object[i].value;
m -= object[i].weight;
}
}
return p;
}
int main(int argc, char *argv[])
{
int i;
int ret;
int W[N] = {3,5,4};
int V[N] = {4,6,5};
OBJECT object[N];
for(i=0;i<N;i++)
{
object[i].weight = W[i] * 1.0;
object[i].value = V[i] * 1.0;
object[i].ratio = (V[i]*1.0)/W[i];
}
sort(object, 0, N-1);
printf("object is:\n");
print_object(object, N);
ret = greed(object, N, TOTAL_V);
printf("max is %d\n", ret);
system("PAUSE");
return 0;
}
|
我这里得出的答案,都不是最优解,呵呵有人会说了,那贪婪算法有个p用...这里是特意为了出线这个次最优解而选择的数据...实际中数据量大的时候,这种次最优解是可以接受的
阅读(846) | 评论(0) | 转发(0) |
