南京邮电大学算法与设计实验二：贪心算法（最全最新，与题目要求一致）-Toy模板网

这篇具有很好参考价值的文章主要介绍了南京邮电大学算法与设计实验二：贪心算法（最全最新，与题目要求一致）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

三、实验原理及内容

实验原理：

1、用贪心法实现求两序列的一般背包问题。要求掌握贪心法思想在实际中的应用，分析一般背包的问题特征，选择算法策略并设计具体算法，编程实现贪心选择策略的比较，并输出最优解和最优解值。

2、用贪心法求解带时限的(单位时间)作业排序问题，求得最优的计算次序以使得作业按

序完成，并收益最大

实验内容：

一般背包问题

标准 1：选取目标函数(总价值)作为量度标准,每次取价值最大的物品装包,不考虑重量.

标准 2：选取重量作为量度标准,每次取重量最小的物体装包,不考虑收益.

标准 3：选取单位重量价值最大的物品装包,即每次选 pi/wi 最大的物品装包.标准最合理, 得到最优解.(正确性有待证明)

基本步骤:

1、首先计算每种物品单位重量的价值 Pi/Wi 并按非增次序进行排序；

2、然后依贪心选择策略，选择单位重量价值最高的物品装入背包。依此策略一直地进行下去，将尽可能多的物品全部装入背包，直到将背包装满。

3、若装入某件物品时，不能全部装下，而背包内的物品总重量仍未达到 W，则根据背包的剩余载重，选择单位重量价值次高的物品并尽可能多地装入背包。

代码实现：

include <iostream>
using namespace::std;

class Knapsack
{
public:
    Knapsack(int mSize, float cap, float *wei, float *prof)//msize为最大重量
    {
        m = mSize;
        w = wei;
        p = prof;
        n = cap;
    }
    void GreedyKnapsack(float *x);


private:
    float m, *w;
    float *p;
    int n;
};

void Knapsack::GreedyKnapsack(float *x){ //前置条件：w[i]已按 p[i]/w[i]的非增次序排序
 int i=0;
 float u=m; //将背包剩余载重量 u 初始化为 m
 for (i=0;i<n;i++)
     x[i]=0; //对解向量 x 初始化
 for (i=0;i<n;i++) { //按最优量度标准选择解分量 xi
     if (w[i]>u)
         break; //若当前物品 i 已无法全部装下，则跳出
     x[i]=1.0; //否则，整个装入当前物品 i
     u=u-w[i];
 } //同时背包剩余载重减 w[i]
 if (i<n)
    x[i]=u/w[i]; //背包剩余空间只够放下当前物品 i 的 x[i]部分
}


//按照单位重量的价值量大小降序排列
void Sort(int n,float *w,float *v)
{
    int i,j;
    float temp1,temp2;
    for(i=1;i<n;i++)
    for(j=1;j<n-i;j++)//冒泡排序
    {
        temp1=v[j]/w[j];
        temp2=v[j+1]/w[j+1];
        if(temp1<temp2)
        {
            swap(w[j],w[j+1]);
            swap(v[j],v[j+1]);
        }
    }
}


int main(){
    int n;
    float m, w[100], p[100];
    float x[100];   //表示最后放入背包的比例
    cout<<"依次输入每件物品的重量和价值量"<<endl;
    cin>>n>>m;
    Knapsack Bag(m, n, w, p);
    //依次输入每件物品的重量和价值量
    for(int i=0;i<n;i++)
        cin>>w[i]>>p[i];
    //按照单位重量的价值量大小降序排列
    Sort(n, w, p);
    Bag.GreedyKnapsack(x);
    for(int i=0;i<n;i++)
            cout<<"重量为"<<w[i]<<"价值量为"<<p[i]<<"的物品"<<"放入的比例为"<<x[i]<<endl;
    return 0;
}

实验结果：

由实验结果可得知背包成功

南京邮电大学算法与设计实验二：贪心算法（最全最新，与题目要求一致）

最小代价生成树

设 G=(V,E)是一个连通带权图，V={1,2,…,n}。构造 G 的一棵最小生成树 F=(U,S)的 Prim

算法的基本步骤是： (U 为正在构造的生成树点集)

1、首先从图的任一顶点起进行，将它加入集合 U 中。如：置 U={1}；

2、然后作如下的贪心选择：每次从与集合 U 相关联的边中（即一个端点在集合中而另一个端点在集合外的各条边中），选出权值 c[i][j]最小的一条作为生成树的一条边，此时满足条件 iU，jV-U，并将集合外的结点 j 加入集合中，表示该点也被所选出的边连通了。

3、这个过程一直进行到 U=V 时为止，这时全部顶点都加入到集合 U 中。在这个过程中选取到的所有边恰好构成 G 的一棵最小生成树。


#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

// A structure to represent a node in adjacency list
struct AdjListNode {
    int dest;
    int weight;
    struct AdjListNode* next;
};


struct AdjList {
    struct AdjListNode*
            head;
};


struct Graph {
    int V;
    struct AdjList* array;
};


struct AdjListNode* newAdjListNode(int dest, int weight)
{
    struct AdjListNode* newNode
            = (struct AdjListNode*)malloc(
                    sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 一个效用函数创建一个图的顶点V
struct Graph* createGraph(int V)
{
    struct Graph* graph
            = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // 创建一个数组的邻接列表。数组的大小V
    graph->array = (struct AdjList*)malloc(
            V * sizeof(struct AdjList));

    //初始化每个邻接表为空,
    //头为零
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// 添加一条边一个无向图
void addEdge(struct Graph* graph, int src, int dest,
             int weight)
{
    // 添加一个从src到桌子边缘。添加一个新节点
    // src的邻接表。节点被添加的
    // beginning
    struct AdjListNode* newNode
            = newAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 因为图是无定向的，所以从dest到src添加一条边。
    newNode = newAdjListNode(src, weight);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 表示一个迷你堆节点的结构
struct MinHeapNode {
    int v;
    int key;
};

// 表示迷你堆的结构
struct MinHeap {
    int size; // 当前存在的堆节点的数量
    int capacity; // 最小堆的容量
    int* pos; // 这是decreaseKey()所需要的。
    struct MinHeapNode** array;
};

struct MinHeapNode* newMinHeapNode(int v, int key)
{
    struct MinHeapNode* minHeapNode
            = (struct MinHeapNode*)malloc(
                    sizeof(struct MinHeapNode));
    minHeapNode->v = v;
    minHeapNode->key = key;
    return minHeapNode;
}


struct MinHeap* createMinHeap(int capacity)
{
    struct MinHeap* minHeap
            = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    minHeap->pos = (int*)malloc(capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode**)malloc(
            capacity * sizeof(struct MinHeapNode*));
    return minHeap;
}


void swapMinHeapNode(struct MinHeapNode** a,
                     struct MinHeapNode** b)
{
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}


void minHeapify(struct MinHeap* minHeap, int idx)
{
    int smallest, left, right;
    smallest = idx;
    left = 2 * idx + 1;
    right = 2 * idx + 2;

    if (left < minHeap->size
        && minHeap->array[left]->key
           < minHeap->array[smallest]->key)
        smallest = left;

    if (right < minHeap->size
        && minHeap->array[right]->key
           < minHeap->array[smallest]->key)
        smallest = right;

    if (smallest != idx) {
        // The nodes to be swapped in min heap
        MinHeapNode* smallestNode
                = minHeap->array[smallest];
        MinHeapNode* idxNode = minHeap->array[idx];

        // Swap positions
        minHeap->pos[smallestNode->v] = idx;
        minHeap->pos[idxNode->v] = smallest;

        // Swap nodes
        swapMinHeapNode(&minHeap->array[smallest],
                        &minHeap->array[idx]);

        minHeapify(minHeap, smallest);
    }
}


int isEmpty(struct MinHeap* minHeap)
{
    return minHeap->size == 0;
}


struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
    if (isEmpty(minHeap))
        return NULL;

    // Store the root node
    struct MinHeapNode* root = minHeap->array[0];

    // Replace root node with last node
    struct MinHeapNode* lastNode
            = minHeap->array[minHeap->size - 1];
    minHeap->array[0] = lastNode;

    // Update position of last node
    minHeap->pos[root->v] = minHeap->size - 1;
    minHeap->pos[lastNode->v] = 0;

    // Reduce heap size and heapify root
    --minHeap->size;
    minHeapify(minHeap, 0);

    return root;
}


void decreaseKey(struct MinHeap* minHeap, int v, int key)
{
    int i = minHeap->pos[v];


    minHeap->array[i]->key = key;


    while (i
           && minHeap->array[i]->key
              < minHeap->array[(i - 1) / 2]->key) {
        // Swap this node with its parent
        minHeap->pos[minHeap->array[i]->v] = (i - 1) / 2;
        minHeap->pos[minHeap->array[(i - 1) / 2]->v] = i;
        swapMinHeapNode(&minHeap->array[i],
                        &minHeap->array[(i - 1) / 2]);


        i = (i - 1) / 2;
    }
}


bool isInMinHeap(struct MinHeap* minHeap, int v)
{
    if (minHeap->pos[v] < minHeap->size)
        return true;
    return false;
}


void printArr(int arr[], int n)
{
    for (int i = 1; i < n; ++i)
        printf("%d - %d\n", arr[i], i);
}

void PrimMST(struct Graph* graph)
{
    int V = graph->V; // 获得图中顶点的数量
    int parent[V]; // 用于存储构建的MST的数组
    int key[V]; // 用来挑选最小权重的关键值
    // 在cut中的边缘
    struct MinHeap* minHeap = createMinHeap(V);
    for (int v = 1; v < V; ++v) {
        parent[v] = -1;
        key[v] = INT_MAX;
        minHeap->array[v] = newMinHeapNode(v, key[v]);
        minHeap->pos[v] = v;
    }
    // 使第0个顶点的键值为0，这样它就会被首先提取。
    // 先被提取出来
    key[0] = 0;
    minHeap->array[0] = newMinHeapNode(0, key[0]);
    minHeap->pos[0] = 0;

    // 最小堆的初始大小等于V
    minHeap->size = V;

    // 在下面的循环中，min heap包含所有的节点
    // 尚未添加到MST中。
    while (!isEmpty(minHeap)) {
        //提取具有最小键值的顶点
        struct MinHeapNode* minHeapNode
                = extractMin(minHeap);
        int u
                = minHeapNode
                        ->v;

        struct AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl != NULL) {
            int v = pCrawl->dest;
            if (isInMinHeap(minHeap, v)
                && pCrawl->weight < key[v]) {
                key[v] = pCrawl->weight;
                parent[v] = u;
                decreaseKey(minHeap, v, key[v]);
            }
            pCrawl = pCrawl->next;
        }
    }
    printArr(parent, V);
}

int main()
{
    // Let us create the graph given in above figure
    int V = 9;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1, 4);
    addEdge(graph, 0, 7, 8);
    addEdge(graph, 1, 2, 8);
    addEdge(graph, 1, 7, 11);
    addEdge(graph, 2, 3, 7);
    addEdge(graph, 2, 8, 2);
    addEdge(graph, 2, 5, 4);
    addEdge(graph, 3, 4, 9);
    addEdge(graph, 3, 5, 14);
    addEdge(graph, 4, 5, 10);
    addEdge(graph, 5, 6, 2);
    addEdge(graph, 6, 7, 1);
    addEdge(graph, 6, 8, 6);
    addEdge(graph, 7, 8, 7);

    PrimMST(graph);

    return 0;
}

实验结果：

南京邮电大学算法与设计实验二：贪心算法（最全最新，与题目要求一致）

测试数据与实验结果：

南京邮电大学算法与设计实验二：贪心算法（最全最新，与题目要求一致）

实验结果与预设结果一致。

带时限的作业排序

有n 个作业，每个作业都有一个截止期限di>0（di 为整数）。每个作业运行时间为1 个单

位时间。每个作业若能够在截止期限内完成，可获得pi>0 的收益。

要求：

得到一种作业调度方案，给出作业的一个子集和该子集的一种排列，使子集中的作业都能

如期完成，并且获得最大的收益。

代码实现：

#include <iostream>
using namespace::std;
//d[]是时间分配，x[]是作业
int JS(int *d, int *x, int n)
{ //设p0≥p1 ≥... ≥pn-1
    int k=0; //(x[0],...,x[k])是当前已入选的作业向量，x[0]一定入选
    x[0]=0;
    for (int j=1;j<n;j++)   //从第二个开始
    {
        int r=k; //变量r 负责从位置k 向前寻找插入位置
        while( r>=0 && d[x[r]]>d[j] && d[x[r]]>r+1)
            r--; //搜索作业j 的插入位置
        if ((r<0 || d[x[r]]<=d[j]) && d[j]>r+1) //若条件不满足，选择下一个作业
        { //已选作业中位置r+1 至k 的作业均可后移
            //且作业j 自身也能在时限内完成
            for (int i=k; i>=r+1; i--) x[i+1]=x[i]; //将x[r]以后的作业后移
            x[r+1]=j; //作业j 插入r+1 位置处
            k++;
        }
    }
    return k;
}
int main(){
    int n;//作业总数
    int d[100],x[100];//d[]表示作业持续时间的数组，x[]表示用于存储选定作业索引的数组
    int i;
    //初始化作业
    cout<<"请输入作业总数"<<endl;
    cin>>n;
    for(i=0;i<n;i++){
        cout<<"请输入第"<<i+1<<"门作业的作业时限:";
        cin>>d[i];
    }
    int k=JS(d,x,n);
    // 输出选定的作业索引和数量
    cout<<"选定的作业索引：";
    for(i = 0; i < k; i++){
        cout<<x[i];
    }
    cout<<endl;
    cout<<"选定的作业数量："<<k<<endl;
    return 0;
}

实验结果：

南京邮电大学算法与设计实验二：贪心算法（最全最新，与题目要求一致）