文档章节

贪心算法

jit-hakase
 jit-hakase
发布于 2017/09/03 16:24
字数 598
阅读 6
收藏 1

#贪心算法 ###最大购买 问题:有N元钱, 有三种商品, 价格分别为150元, 200元, 350元, 在最大购买下最少能剩下多少钱. 思路:350=150+200, 排除此商品, 全购买150元的商品, 如果还有余钱, 把150元的商品换成200元. python code

N = 580
cnt = N//150
sum = N%150

while sum>=50 and cnt>0:
    sum -= 50
    cnt -= 1

print(sum)

###最少支付 问题: 有n个坑, 体积为v, 有m堆沙子, 体积为x, 用体积为x的沙子可以填满深度<=x的坑, 但是要支付x元, 如何支付最少的钱?(不能组合沙子填坑.) 思路: 对坑和沙子的序列进行排序, 依次尝试是否能填满.

  • python code*
P = [7, 3, 9, 5, 1]
S = [5, 4, 7, 8, 2, 3, 9]

P.sort()
S.sort()

sum, begin = 0, 0

for i in range(len(P)):
    for j in range(begin, len(S)):
        if S[j] >= P[i]:
            sum += S[j]
            begin = j+1
            break
    else:
        print('no')
        break
else:
    print(sum)

###最多不相交区间 问题: 有N个区间(a, b), 尽量选择多个区间, 他们之间没有公共点. 思路: 按b对区间进行排序, 不管是a1>a2还是a1<a2, 选择(a1,b1)更划算, 选择(a1, b1)后, 余下的区间又是一个新区间组, 递归此步骤. python code

class Area:
    def __init__(self, a, b):
        self.a, self.b = a, b

A = [
    Area(2, 5), Area(1, 4), Area(2, 3), Area(5, 6),
    Area(1, 2), Area(3, 5), Area(3, 6), Area(1, 3)
]

A.sort(key=lambda x: x.b)

max_b = 0

for item in A:
    if item.a >= max_b:
        print(item.a, item.b)
        max_b = item.b

###Huffman树 问题: 给定一组序列, 2个数的和合成1个父节点, 生成一颗权值最小的树, 第N层权值为N. 思路:每次选择序列中最小的2个数构成左节点和右节点, 再把它们的父节点的值放进序列, 递归此步骤. python code 构造节点核心算法

from queue import PriorityQueue
A = [4, 2, 1, 5, 9, 8, 6]
Q = PriorityQueue()

for item in A:
    Q.put(item)

while Q.qsize() > 1:
    min1, min2 = Q.get(), Q.get()
    Q.put(min1+min2)
    print(min1, min2)

print(Q.get())

构造树 先序遍历输出结果

from queue import PriorityQueue

class Tree:
    def __init__(self, lc, rc, data):
        self.lc, self.rc, self.data = lc, rc, data

    def __lt__(self, other):
        return True if other.data > self.data else False

def show(node):
    if node:
        print(node.data)
        show(node.lc)
        show(node.rc)

A = [4, 2, 1, 5, 9, 8, 6]
Q = PriorityQueue()

for item in A:
    Q.put(Tree(None, None, item))

while Q.qsize() > 1:
    lc, rc = Q.get(), Q.get()
    parent = Tree(lc, rc, lc.data+rc.data)
    Q.put(parent)

show(Q.get())

© 著作权归作者所有

上一篇: 博弈论
下一篇: 分治算法
jit-hakase
粉丝 3
博文 26
码字总数 30408
作品 0
南京
程序员
私信 提问

暂无文章

AliOS Things 3.0 应用开发指南

目录 应用开发框架介绍 使用条件 快速开始 第一步:下载AliOS Things 3.0源码 第二步:添加AOS_SDK_PATH环境变量 第三步:AliOS Studio中创建应用工程 编译、烧录、调试 其他说明 参考文档 ...

阿里云官方博客
37分钟前
3
0
日期和月份的计算

需求一 根据 【首次任务开始时间】和【任务间隔时间】和【每个任务持续时间】和【任务次数】计算出每个任务的时间 // 数据计算方法 async dateCalculation() { const firstD...

沉迷代码我爱学习
42分钟前
2
0
Spring Cloud Gateway 之请求坑位[微服务IP不同请求会失败]

问题产生背景 在使用Spring Cloud Gateway过程中,希望配置多Routes映射不同的微服务,因为Gateway 和Zuul的访问路径不同(zuul 会带有服务service Id),造成错误。 现象表现 问题定位 认为是...

IsaacZhang
53分钟前
5
0
Vue nodejs商城项目-搭建express框架环境

本文转载于:专业的前端网站➯Vue nodejs商城项目-搭建express框架环境 1.express-project 搭建express框架环境 安装express generator生成器 通过生成器自动创建项目 配置分析 安装 cnpm i -...

前端老手
今天
3
0
maven项目A引入maven项目B的jar包

首先打开 项目B 的 pom 文件,加入如下配置 <build> <plugins> <plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-compiler-plugin<......

嘴角轻扬30
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部