华为OD机考 书籍叠放 python 动态规划
给定一组书的长宽,并且只有当一本书的长宽同时小于另一本书的长宽时,两书才能叠放在一起,求该组书中最多能有多少本书叠放在一起
输入:[[20,16],[15,11],[10,10],[9,10]]
输出:3,前三本可叠放在一起
以下为排序+动态规划的解法:
N = 100 book_l = [[random.randint(1, N), random.randint(1, N)] for _ in range(N)] print(book_l) book_l.sort(reverse=True) print(book_sort) s = time.time() dp = [1 for i in range(len(book_sort))] # bp每一项表示该书底下能叠起来的书的最大值,默认为1,即自己 for i, book in enumerate(book_sort): if i == 0: continue book_pres = book_sort[:i][::-1] # 判断本书能叠在前面哪本书上,不考虑i后面的书,列表排序好后肯定是叠不上的 #倒序是为了下面判断节省时间 for j, book_pre in enumerate(book_pres): if book[0] < book_pre[0] and book[1] < book_pre[1]: a = dp[i - j - 1] + 1 # 本书能叠在某本书上,则本书在某本书的数量上+1,j从0开始,所以-1 dp[i] = max(a, dp[i]) # 取最大值 if max(dp[:i]) < dp[i]: # 若本书为dp中最大值,肯定不能再大了,为节省时间不用再往前判断 break print(max(dp)) print(time.time() - s)
下面这个代码也是自己写的,有点像贪心的解法,但是不会获得最优解,数据量大的话差别就很明显。
book_l = [[10, 7], [1, 7], [10, 8], [13, 9], [1, 2], [20, 20], [14, 17], [20, 16], [20, 13], [15, 18], [11, 9], [11, 8], [19, 16]] sorted_book = list() while book_l: book_below_l = list() print('book_l', book_l) for i in range(len(book_l)): # 遍历找出每本书底下能放多少本书,并存入book_below -> [size,size,size,..] book_below = list() count = 0 for ii in range(len(book_l)): # 判断本书可以叠在几本书上 if book_l[i][0] < book_l[ii][0] and book_l[i][1] < book_l[ii][1]: # or book_l[i][0] < book_l[ii][1] and book_l[i][1] < book_l[ii][0] # 若考虑书籍旋转,在此代码增加判断条件即可 book_below.append(book_l[ii]) # 将book_below 存入 book_below_l -> [[size,size,size,..],[size,size,size,..]] book_below_l.append(book_below) book_num_l = [len(l) for l in book_below_l] # book_below_l 中每组列表的长度 min_book_index = book_num_l.index(max(book_num_l)) # 最上边的书,下面可以叠放的书最多,找到其在book_l中的索引 min_book = book_l[min_book_index] # 获得最上边的书 book_l = book_below_l[min_book_index] # 获得新的book_l 为 min_book 底下可叠放书的列表 sorted_book.append(min_book) # 将book_l 中的min_book 存入 sorted_book 为整理好的书籍列表 print(len(sorted_book), sorted_book)