程序员经验分享-hwhale

算法设计与实现--贪心篇

2023-12-05

贪心算法

贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法，以期望能够通过一系列局部最优的选择达到全局最优。贪心算法的关键是定义好局部最优的选择，并且不回退，即一旦做出了选择，就不能撤销。

一般来说，贪心算法适用于满足以下两个条件的问题：

  1. 最优子结构性质（Optimal Substructure）： 问题的最优解包含了其子问题的最优解。这意味着可以通过子问题的最优解来构造原问题的最优解。
  2. 贪心选择性质（Greedy Choice Property）： 当考虑做某个选择时，贪心算法总是选择当前看起来最优的解，而不考虑其他可能性。这个选择是局部最优的，希望通过这种选择能够达到全局最优。

关键的两步
提出贪心策略：观察问题特征，构造贪心选择
证明贪心正确：假设最优方案，通过替换证明

相关问题

1、部分背包问题

问题描述

部分背包问题是背包问题的一个变体，与 0-1 背包问题和完全背包问题不同。在部分背包问题中，每个物品可以选择一部分放入背包，而不是必须选择放入或不放入。

以下是部分背包问题的算法思想：

  1. 计算单位价值： 对每个物品计算单位价值，单位价值等于物品的价值/物品的重量。

    单位价值=物品的价值/物品的重量

  2. 按单位价值降序排序： 将所有物品按照单位价值降序排列，这样就可以优先选择单位价值较高的物品。

  3. 贪心选择： 从排好序的物品列表中按顺序选择物品放入背包。对于每个物品，可以选择一部分（即部分背包），而不必全部选择。

  4. 计算总价值： 根据所选物品计算放入背包的总价值

算法实现 

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

// 物品的结构
struct Item{
	int weight;  // 物品重量 
	int value;   // 物品价值 
}; 

// 1计算单位价值
double computeUnitValue(struct Item item){
	double result = item.value/item.weight;
	return result;
} 

// 2 按单位价值进行降序排序
// 在这个比较函数中，参数的类型为 const void*，
//这是因为这个函数是用于通用排序算法（例如 qsort）的，
//而通用排序算法不关心待排序元素的具体类型
int compare(const void* a,const void* b) {
	// *(struct Item*) 
	// 这是一种类型转换，将通用指针 const void* 转换为具体类型 struct Item*
	 double unitValueA = computeUnitValue(*(struct Item*)a);
	 double unitValueB = computeUnitValue(*(struct Item*)b);
	 
	 if(unitValueA < unitValueB){
	 	return 1;
	 }else if(unitValueA > unitValueB){
	 	return -1;
	 }else{
	 	return 0;
	 }
}

// 3 贪心算法
double fractionalKnapsack(struct Item items[],int n,int vtl) {
	// 跟据单位价值降序排列 
	qsort(items,n,sizeof(struct Item),compare);
	
	// 最大总价值 
	double maxValue = 0.0;  
	
	// 从排好序的物品列表中贪心选择，选择单位价值大的物品
	// 此时的items 是已经是跟据单位价值降序排序的，所以items[0] 是单位价值最大的物品 
	for(int i=0;i<n;i++){
		//  如果背包的容量>=物品的容量，则贪心策略，将整个物品放入背包 
		if(vtl>=items[i].weight){
			maxValue += items[i].value;  //  最大的价值更新 
			vtl -= items[i].weight;		// 背包容量更新 
		}else{ // 如果背包容量没法将整个物品放入，则计算他的单位价值，然后单位价值*剩余背包容量 
			maxValue += computeUnitValue(items[i])*vtl;
			break;
		}
	} 
	
	return maxValue;
}


// 主函数
int main() {
    struct Item items[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(items) / sizeof(items[0]);
    int vtl = 50; // 背包容量 

    double maxValue = fractionalKnapsack(items, n, capacity);

    printf("Maximum value that can be obtained = %.2f\n", maxValue);

    return 0;
}

2、哈夫曼编码

哈夫曼编码（Huffman Coding）是一种基于字符出现频率的编码方式，它通过使用较短的比特序列来表示出现频率较高的字符，从而实现对数据的高效压缩。这种编码方式是由大卫·哈夫曼（David A. Huffman）于1952年提出的。

哈夫曼编码的基本思想：

  1. 构建哈夫曼树（Huffman Tree） ：
    • 对于需要编码的字符，根据其出现频率构建一个哈夫曼树。
    • 频率越高的字符在树中离根越近，频率越低的字符在树中离根越远。（首先选择最小的两个频）
  2. 分配编码 ：
    • 遍历哈夫曼树的路径，给每个字符分配一个独一无二的二进制编码。
    • 一般来说，向左走表示添加一个0，向右走表示添加一个1。
  3. 生成哈夫曼编码表 ：
    • 将每个字符与其对应的二进制编码建立映射关系，形成哈夫曼编码表。

算法实现 

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

// 哈夫曼树节点结构
struct HuffmanNode {
    char data;
    int frequency;
    struct HuffmanNode* left;
    struct HuffmanNode* right;
};

// 字符频率表结构
struct FrequencyTable {
    char data;
    int frequency;
};

// 优先队列中的元素
struct PriorityQueueElement {
    struct HuffmanNode* node;
    struct PriorityQueueElement* next;
};

// 优先队列结构
struct PriorityQueue {
    struct PriorityQueueElement* front;
};

// 初始化优先队列
void initPriorityQueue(struct PriorityQueue* pq) {
    pq->front = NULL;
}

// 插入元素到优先队列
void insertPriorityQueue(struct PriorityQueue* pq, struct HuffmanNode* node) {
    struct PriorityQueueElement* newElement = (struct PriorityQueueElement*)malloc(sizeof(struct PriorityQueueElement));
    newElement->node = node;
    newElement->next = NULL;

    if (pq->front == NULL || node->frequency < pq->front->node->frequency) {
        newElement->next = pq->front;
        pq->front = newElement;
    } else {
        struct PriorityQueueElement* current = pq->front;
        while (current->next != NULL && current->next->node->frequency <= node->frequency) {
            current = current->next;
        }
        newElement->next = current->next;
        current->next = newElement;
    }
}

// 从优先队列中取出最小元素
struct HuffmanNode* extractMinPriorityQueue(struct PriorityQueue* pq) {
    if (pq->front == NULL) {
        return NULL;
    }

    struct HuffmanNode* minNode = pq->front->node;
    struct PriorityQueueElement* temp = pq->front;
    pq->front = pq->front->next;
    free(temp);

    return minNode;
}

// 构建哈夫曼树
struct HuffmanNode* buildHuffmanTree(struct FrequencyTable frequencies[], int n) {
    struct PriorityQueue pq;
    initPriorityQueue(&pq);

    // 初始化优先队列，每个节点作为一个单独的树
    for (int i = 0; i < n; ++i) {
        struct HuffmanNode* newNode = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
        newNode->data = frequencies[i].data;
        newNode->frequency = frequencies[i].frequency;
        newNode->left = newNode->right = NULL;
        insertPriorityQueue(&pq, newNode);
    }

    // 重复合并节点，直到队列中只剩下一个节点，即哈夫曼树的根
    while (pq.front->next != NULL) {
        struct HuffmanNode* leftChild = extractMinPriorityQueue(&pq);
        struct HuffmanNode* rightChild = extractMinPriorityQueue(&pq);

        struct HuffmanNode* newNode = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
        newNode->data = '\0'; // 内部节点没有字符数据
        newNode->frequency = leftChild->frequency + rightChild->frequency;
        newNode->left = leftChild;
        newNode->right = rightChild;

        insertPriorityQueue(&pq, newNode);
    }

    // 返回哈夫曼树的根节点
    return extractMinPriorityQueue(&pq);
}

// 生成哈夫曼编码
void generateHuffmanCodes(struct HuffmanNode* root, int code[], int top) {
    if (root->left != NULL) {
        code[top] = 0;
        generateHuffmanCodes(root->left, code, top + 1);
    }

    if (root->right != NULL) {
        code[top] = 1;
        generateHuffmanCodes(root->right, code, top + 1);
    }

    if (root->left == NULL && root->right == NULL) {
        printf("Character: %c, Code: ", root->data);
        for (int i = 0; i < top; ++i) {
            printf("%d", code[i]);
        }
        printf("\n");
    }
}

// 主函数
int main() {
    struct FrequencyTable frequencies[] = {{'A', 2}, {'B', 1}, {'C', 1}, {'D', 1},{'E',4}
	};
    int n = sizeof(frequencies) / sizeof(frequencies[0]);

    struct HuffmanNode* root = buildHuffmanTree(frequencies, n);

    int code[100];
    int top = 0;

    printf("Huffman Codes:\n");
    generateHuffmanCodes(root, code, top);

    return 0;
}

3、活动选择问题

活动选择问题（Activity Selection Problem）是一个经典的贪心算法问题， 也称为区间调度问题 。给定一组活动，每个活动都有一个开始时间和结束时间，目标是选择出最大可能的互不相交的活动子集。

以下是活动选择问题的算法思想：

  1. 将活动按照结束时间的先后顺序进行排序。
  2. 选择第一个活动作为初始活动，并将其加入最终选择的活动子集。
  3. 从第二个活动开始，依次判断每个活动是否与已选择的活动相容（即结束时间是否早于下一个活动的开始时间），如果相容，则将该活动加入最终选择的活动子集。
  4. 重复步骤3，直到遍历完所有活动。

通过贪心策略， 每次选择结束时间最早的活动 ，可以确保选择的活动子集最大化。因为如果一个活动与已选择的活动相容，那么它一定是结束时间最早的活动，选择它不会影响后续活动的选择。
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码实现

该算法的核心就是 每次选择结束时间最早的活动 

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

// 活动结构
struct Activity {
    int start;
    int end;
};

// 比较函数，用于按结束时间升序排序
int compare(const void* a, const void* b) {
    return ((struct Activity*)a)->end - ((struct Activity*)b)->end;
}

// 活动选择算法
void activitySelection(struct Activity activities[], int n) {
    // 按结束时间升序排序
    qsort(activities, n, sizeof(struct Activity), compare);

    // 第一个活动总是被选择
    printf("Selected activity: (%d, %d)\n", activities[0].start, activities[0].end);

    // 从第二个活动开始选择
    int lastActivity = 0;
    for (int i = 1; i < n; ++i) {
        // 如果活动的开始时间晚于或等于上一个已选择活动的结束时间，选择该活动
        if (activities[i].start >= activities[lastActivity].end) {
            printf("Selected activity: (%d, %d)\n", activities[i].start, activities[i].end);
            lastActivity = i;
        }
    }
}

// 主函数
int main() {
    struct Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}};
    int n = sizeof(activities) / sizeof(activities[0]);

    printf("Activity schedule:\n");
    activitySelection(activities, n);

    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

算法

贪心算法

c语言

c

算法设计与实现--贪心篇 的相关文章

  • 没有特殊字符的密码验证器

    我是 RegEx 的新手 已经进行了大量搜索 但没有找到任何具体内容 我正在编写一个验证密码字符串的正则表达式 可接受的字符串必须至少具有 4 种字符类型中的 3 种 数字 小写字母 大写字母 特殊字符 我对包含有一个想法 也就是说 如果这

  • 机器Epsilon精度差异

    我正在尝试计算 C 中双精度数和浮点数的机器 epsilon 值 作为学校作业的一部分 我在 Windows 7 64 位中使用 Cygwin 代码如下 include

  • std::list 线程push_back、front、pop_front

    std list 线程安全吗 我假设不是这样 所以我添加了自己的同步机制 我认为我有正确的术语 但我仍然遇到问题 每个函数都由单独的线程调用 Thread1 不能等待 它必须尽可能快 std list

  • std::vector 与 std::stack

    有什么区别std vector and std stack 显然 向量可以删除集合中的项目 尽管比列表慢得多 而堆栈被构建为仅后进先出的集合 然而 堆栈对于最终物品操作是否更快 它是链表还是动态重新分配的数组 我找不到关于堆栈的太多信息 但

  • free 和 malloc 在 C 中如何工作？

    我试图弄清楚如果我尝试 从中间 释放指针会发生什么 例如 看下面的代码 char ptr char malloc 10 sizeof char for char i 0 i lt 10 i ptr i i 10 ptr ptr ptr pt

  • 从经典 ASP 调用 .Net C# DLL 方法

    我正在开发一个经典的 asp 项目 该项目需要将字符串发送到 DLL DLL 会将其序列化并发送到 Zebra 热敏打印机 我已经构建了我的 DLL 并使用它注册了regasm其次是 代码库这使得 IIS 能够识别它 虽然我可以设置我的对象

  • 对类 static constexpr 结构的未定义引用，g++ 与 clang

    这是我的代码 a cp p struct int2 int x y struct Foo static constexpr int bar1 1 static constexpr int2 bar2 1 2 int foo1 return

  • C++ 多行字符串原始文字[重复]

    这个问题在这里已经有答案了 我们可以像这样定义一个多行字符串 const char text1 part 1 part 2 part 3 part 4 const char text2 part 1 part 2 part 3 part 4

  • 需要帮助优化算法 - 两百万以下所有素数的总和

    我正在尝试做一个欧拉计划 http projecteuler net问题 我正在寻找 2 000 000 以下所有素数的总和 这就是我所拥有的 int main int argc char argv unsigned long int su

  • WPF 数据绑定到复合类模式？

    我是第一次尝试 WPF 并且正在努力解决如何将控件绑定到使用其他对象的组合构建的类 例如 如果我有一个由两个单独的类组成的类 Comp 为了清楚起见 请注意省略的各种元素 class One int first int second cla

  • 人脸 API DetectAsync 错误

    我想创建一个简单的程序来使用 Microsoft Azure Face API 和 Visual Studio 2015 检测人脸 遵循 https social technet microsoft com wiki contents ar

  • 为什么 isnormal() 说一个值是正常的，而实际上不是？

    include

  • 如何在 Android 中使用 C# 生成的 RSA 公钥？

    我想在无法假定 HTTPS 可用的情况下确保 Android 应用程序和 C ASP NET 服务器之间的消息隐私 我想使用 RSA 来加密 Android 设备首次联系服务器时传输的对称密钥 RSA密钥对已在服务器上生成 私钥保存在服务器

  • 编译时展开 for 循环内的模板参数？

    维基百科 here http en wikipedia org wiki Template metaprogramming Compile time code optimization 给出了 for 循环的编译时展开 我想知道我们是否可以

  • 相当于Linux中的导入库

    在 Windows C 中 当您想要链接 DLL 时 您必须提供导入库 但是在 GNU 构建系统中 当您想要链接 so 文件 相当于 dll 时 您就不需要链接 为什么是这样 是否有等效的 Windows 导入库 注意 我不会谈论在 Win

  • 使用特定参数从 SQL 数据库填充组合框

    我在使用参数从 sql server 获取特定值时遇到问题 任何人都可以解释一下为什么它在 winfom 上工作但在 wpf 上不起作用以及我如何修复它 我的代码 private void UpdateItems COMBOBOX1 Ite

  • 为什么 std::uint32_t 与 uint32_t 不同？

    我对 C 有点陌生 我有一个编码作业 很多文件已经完成 但我注意到 VS2012 似乎有以下语句的问题 typedef std uint32 t identifier 不过 似乎将其更改为 typedef uint32 t identifi

  • 指针和内存范围

    我已经用 C 语言编程有一段时间了 但对 C 语言还是很陌生 有时我对 C 处理内存的方式感到困惑 考虑以下有效的 C 代码片段 const char string void where is this pointer variable l

  • Mono 应用程序在非阻塞套接字发送时冻结

    我在 debian 9 上的 mono 下运行一个服务器应用程序 大约有 1000 2000 个客户端连接 并且应用程序经常冻结 CPU 使用率达到 100 我执行 kill QUIT pid 来获取线程堆栈转储 但它总是卡在这个位置

  • 现代编译器是否优化乘以 1 和 -1

    如果我写 template

随机推荐

热门标签