贪婪算法:
1、不追求最优解,故不穷举所有可能性,故效率高;
2、在某些情况,会成为最优解,如找钱时要求纸币数量最少。
求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
马踏棋盘、背包装重的场景
#include <iostream>
#include <string>
using namespace std;
int greedy(int tag, int *p, int size);
int main(int argc, char *argv[])
{
int weight[10] = {90,80,70,60,50,40,30,20,10,5};
cout << greedy(225, weight, 10) << endl;
return 0;
}
int greedy(int tag, int *p, int size)
{
// 假设数组P由降序排列
int count = 0;
for (int i = 0; i < size; i++)
{
if (tag >= p[i])
{
cout << i << ":" << p[i] << endl;
count += p[i];
tag -= p[i];
}
}
return count;
}
分享到:
相关推荐
题目1:设 n 为一自然数,n 可以分解成若干个不同的自然数的和,这样的分法有很多种,比如 n=10, 10 可以分解为:10=5+4+1; 10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4;10=7+2+1; 10=6+3+1;…。在所有这些分法中,各...
背包问题描述如下: 已知 背包容量M=120 ...(1) 按三种不同的量度标准分别计算所得最大总效益,然后比较哪个最大 1. 按效益值由大到小取物品. 2. 按重量值由小到大取物品 3.按比值pi/wi的值由大到小取物品
属于算法设计的贪心算法PPT格式,方便与大家更好地学习
由此萌发一种有效的贪心策略: 若能够让A方取走“数和较大大的奇(或偶)位置上的所有数”,则A方必胜。这样,取数问题边对应于一个简单问题:让A方取奇偶位置中数和较大的一半数。设j为A取数的奇偶位置标志,则j=0...
over_lap开始不能取对tm标准差影响最大的,应该直接用tm最大上的 over_lap过程最多截取多少,两个小片段之间最大是多少 为了不影响两个片段之间,现在只是对每个片段处理 最后一段不够最小长度不管他 -----------...
这是通过贪心算法实现的:表示总是从最大的斐波那契数 <= N 开始。 在这里,我使用斐波那契数的定义为: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2)。 例如:N = 100 = 89 + 8 + 3。 此代码输出正整数 N 的 ...
9.1 最小值和最大值 9.2 以期望线性时间做选择 9.3 最坏情况线性时间的选择 第三部分 数据结构 引言 第10章 基本数据结构 10.1 栈和队列 10.2 链表 10.3 指针和对象的实现 10.4 有根树的表示 第11...
4.2.3 贪心算法与动态规划算法的差异 4.3 最优装载 4.4 哈夫曼编码 4.4.1 前缀码 4.4.2 构造哈夫曼编码 4.4.3 哈夫曼算法的正确性 4.5 单源最短路径 4.5.1 算法基本思想 4.5.2 算法的正确性和计算复杂性 4.6 最小...
4.4.1 取正合幂时的证明 4.4.2 上取整函数和下取整函数 第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 5.4 概率分析和指示器随机变量的进一步使用 5.4.1 生日悖论 5.4.2 球与盒子 5.4.3 ...
4.4.1 取正合幂时的证明 4.4.2 上取整函数和下取整函数 第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 5.4 概率分析和指示器随机变量的进一步使用 5.4.1 生日悖论 5.4.2 球与盒子 5.4.3 ...
4.4.1 取正合幂时的证明 4.4.2 上取整函数和下取整函数 第5章 概率分析和随机算法 5.1 雇用问题 5.2 指示器随机变量 5.3 随机算法 5.4 概率分析和指示器随机变量的进一步使用 5.4.1 生日悖论 5.4.2 球与盒子 5.4.3 ...
9.1 最小值和最大值 9.2 以期望线性时间做选择 9.3 最坏情况线性时间的选择 第三部分 数据结构 引言 第10章 基本数据结构 10.1 栈和队列 10.2 链表 10.3 指针和对象的实现 10.4 有根树的表示 第11...
51.cpp //最大子段和 52.cpp //map应用 53.cpp //ASCII码排序 54.cpp //我的排序 55.cpp //隐藏的时间 56.cpp //好年份 57.cpp //最大最小值 58.cpp //由两天推日期 59.cpp //目标和 60.cpp //统计字符 xiao6 61.cpp...
leetcode双人赛 1 前言 项目为习题册攻略,已完结。可配合书籍或笔记,系统学习算法。 题量:约200道,代码注释内含详解。...最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧
16.从数组中找出最接近给出数值的三数和,先排序,取定第一个数,再首尾取值,往中间移动,贪心。 17.回溯,无递归版。 18.同三数和,不过前两数通过枚举取定。 19.删除链表的倒数第n个元素。使用两相距n个元素的...
最大独立集的贪心算法简易实现,可以快速求取节点数量较少的最大独立集问题。
第三章 贪心 3.1排队接水 3.2智力大冲浪 3.3取火柴游戏 3.4等待时间 3.5加工生产调度 3.6最大乘积 3.7种树 3.8餐巾 3.9马拉松接力赛 3.10线性存储问题 3.11扇区填数 第四章 分治 4.1取余运算 4.2地毯...
双指针:循环计数双指针,小i小j需检查引申:最大连续不重复子序列,序列元素目标和,判断子序列 位运算:取出k位二进制(n >> k&1),返回最后1位置(x&-x) 离散化:排序去重加二分,区间由大化为小 区间合并:...
贪心法 2.2.1 硬币问题 2.2.2 区间问题 2.2.3 字典序最小问题 2.2.4 其他例题 2.3 记录结果再利用的“动态规划” 2.3.1 记忆化搜索与动态规划 2.3.2 进一步探讨递推关系 2.3.3 有关计数问题的DP 2.4 加工并存储数据...