华为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) 
投递小红书等公司10个岗位 >
