Python编程之数据结构与算法练习_011

Stella981
• 阅读 435

练习内容:

1.创建一个类,实现优先级队列功能。
2.使用优先级队列求解IPO问题。

IPO问题:
输入:参数1:正数数组costs;参数2:正数数组profits;参数3:正数k;参数4,正数m

costs[i]表示i号项目的花费;
profits[i]表示i号项目在扣除花费之后还能挣到的钱;
k表示你不能并行,只能串行的最多做k个项目;
m表示你最初的资金;

说明:你每做完一个项目,马上获得的收益,可以支持你去做下一个项目。
输出:你最后获得的最大钱数。

1.实现优先级队列

 1 __author__ = 'Orcsir'
 2 
 3 
 4 class PriorityQueue:
 5     def __init__(self, comparator=lambda x, y: x > y):
 6         self._lst = []
 7         self.comparator = comparator
 8 
 9     def __heap_insert(self, index):
10         array = self._lst
11         while index != 0 and self.comparator(array[index], array[(index - 1) >> 1]):
12             array[index], array[(index - 1) >> 1] = array[(index - 1) >> 1], array[index]
13             index = (index - 1) >> 1
14 
15     def __heap_ify(self, index, size):
16         array = self._lst
17         left = 2 * index + 1
18         while left < size:
19             # 选出左右孩子中的最值
20             largest = left
21             right = left + 1
22             if right < size:
23                 largest = left if self.comparator(array[left], array[right]) else right
24 
25             if self.comparator(array[index], array[largest]):
26                 break
27 
28             array[index], array[largest] = array[largest], array[index]
29             index = largest
30             left = 2 * index + 1
31 
32     def is_empty(self):
33         return True if len(self._lst) == 0 else False
34 
35     def add(self, obj):
36         self._lst.append(obj)
37         self.__heap_insert(len(self._lst) - 1)
38 
39     def pop(self):
40         self._lst[0], self._lst[-1] = self._lst[-1], self._lst[0]
41         obj = self._lst.pop()
42         self.__heap_ify(0, len(self._lst))
43         return obj
44 
45     def peek(self):
46         return self._lst[0]
47 
48     poll = pop

2.创建数据类,用于描述每一个项目

1 class Project:
2     __slots__ = ("cost", "profit")
3 
4     def __init__(self, cost, profit):
5         self.cost = cost
6         self.profit = profit

3.求解IPO问题。策略:建立两个优先级队列:最小花费堆,最大收益堆。根据资金持续解锁花费堆,并向收益堆中发货

 1 def max_heap_comparator(obj1, obj2):
 2     return obj1.profit > obj2.profit  # 大根堆
 3 
 4 
 5 def min_heap_comparator(obj1, obj2):
 6     return obj1.cost < obj2.cost  # 小根堆
 7 
 8 
 9 def findMaximizedCapital(costs: list, profits: list, k: int, m: int) -> int:
10     min_cost_heap = PriorityQueue(min_heap_comparator)
11     max_profit_heap = PriorityQueue(max_heap_comparator)
12 
13     for cost, profit in zip(costs, profits):
14         min_cost_heap.add(Project(cost, profit))
15 
16     for i in range(0, k):
17         while not min_cost_heap.is_empty() and min_cost_heap.peek().cost <= m:
18             obj = min_cost_heap.pop()
19             max_profit_heap.add(obj)
20 
21         if max_profit_heap.is_empty():
22             break
23         m += max_profit_heap.poll().profit
24     return m

4. 简单测试代码

1 if __name__ == '__main__':        
2     costs = [2, 10, 14, 1]
3     profits = [5, 20, 8, 10]
4     k = 4
5     m = 15
6     ret = 0
7     ret = findMaximizedCapital(costs, profits, k, m)
8     print(ret)
点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4天前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
5个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这