成为最伟大的塔楼建造者
成为最伟大的塔楼建造者
提问于 2014-12-19 20:08:16
我正在努力学习如何在python中编写正确的代码，并偶然发现了以下问题。
鲍勃得到了一组积木
b，以及一组要建造的n塔。既然我们在共产的土地上，塔楼应该有尽可能多的高度。问题是，你最多只能得到300秒钟的时间来建造塔楼。目标是将塔高的std降到最低。
假设您得到了以下向量
bricks = [8 8 8 6 6 4 4 4 4 3 3 2]并要求建造5座塔楼。问题的一个输出可以是
8 4 0
8 4 0
8 4 0
6 4 2
6 3 3它的性病是std = ([12-12]^2+[12-12]^2+...+[12-12]^2)^1/2=0。对于3座塔，输出应该是
8 4 4 4
8 6 3 3
8 6 4 2这也是最优的。注:然而，我并不是在要求最优的解决方案。因此，这与背包问题类似。但这里的目标不是把每个背包装满到边沿，而是让每个背包尽可能接近重量。
我想出了两个可能的密码
def TowerGreed(bricks,nTower):
bricks.sort(reverse=True)
lengthBricks = len(bricks)
if lengthBricks > nTower:
Tower = [[] for i in range(0,nTower)]
for i in range(0,lengthBricks):
if i < nTower:
Tower[i].append(bricks[i])
elif i == nTower:
Height = bricks[0:nTower]
Tower[i-1].append(bricks[i])
Height[nTower-1] = bricks[i] + Height[nTower-1]
else:
lowest = Height.index(min(Height))
Tower[lowest].append(bricks[i])
Height[lowest] = bricks[i] + Height[lowest]
return Tower这是一个标准的贪婪算法。它首先对元素进行排序，然后在每个塔上添加一个元素。然后开始检查哪座塔是最小的。最小的塔被赋予下一个部分。
下面给出了上述代码的修改版本
def towerGreedImproved(bricks,numberTowers):
# First we sort the number of bricks from greatest to smallest
bricks.sort(reverse = True)
# Only runs the algorithm if we have more bricks than towers to build
if len(bricks) >= numberTowers:
Towers = [[] for i in range(0,numberTowers)] #Empty vector [[],[],...]
Height = [0] * numberTowers # Zero vector [0,0,...]
avgHeight = sum(bricks)/numberTowers
""" Loops through each tower, adds elements until that tower is just
bellow the average tower height """
for j in range(0,numberTowers):
while Height[0] + bricks[0] < avgHeight:
Towers[j].append(bricks[0])
Height[j] = bricks[0] + Height[j]
del bricks[0]; #Deletes used bricks
for n in bricks:
lowest = Height.index(min(Height))
Towers[lowest].append(n)
Height[lowest] = n + Height[lowest]
print(Towers)
return Towers在这里，我们也从分拣砖块开始，但区别是我们一次只建一座塔。我们在达到平均塔高之前就停止了建筑。这个平均值是砖块除以正在建造的塔数的总和。
第三种选择是随机化输入。上面的代码对于大型向量来说有点慢。为了测试我的代码，我尝试了以下三个向量。2个座塔，3个座塔，finnaly 23座塔.由于更熟悉MATLAB，我编写了以下代码段。但是，我不太清楚如何将其应用到python中，也不知道它是否提供了任何改进。
作为编写适当代码的初学者，我有几个问题
- 我可以对我的编码风格做哪些改进？
- 人们谈论这个问题的动态解决方案。对于这个问题有更好的算法吗？
- 如何确定哪种算法最适合给定的数据集？
回答 2
Code Review用户
回答已采纳
发布于 2014-12-20 03:00:56
也许：
def towerGreedImproved(bricks, numberTowers):
# First we sort the number of bricks from greatest to smallest
obricks = list(bricks)
obricks.sort(reverse = True)
# Only runs the algorithm if we have more bricks than towers to build
if len(obricks) < numberTowers:
return obricks
towers = tuple([] for i in range(numberTowers)) # Empty vector ([],[],...)
height = [0] * numberTowers # Zero vector [0,0,...]
avgHeight = sum(obricks)/numberTowers
""" Loops through each tower, adds elements until that tower is just
below the average tower height """
for j in range(numberTowers):
while height[0] + obricks[0] < avgHeight:
# Deletes used bricks
brick = obricks.pop(0)
towers[j].append(brick)
height[j] += brick
for n in obricks:
lowest = min(enumerate(height), key = lambda kv: kv[1])[0]
towers[lowest].append(n)
height[lowest] += n
return towers
bricks = (8, 8, 8, 6, 6, 4, 4, 4, 4, 3, 3, 2)
print(towerGreedImproved(bricks, 5))值得一提的是：
- Python变量名应为小写。
- 咀嚼某人的输入列表可不太好--复制一份
- 塔可以是一个元组，因为我们不期望内容改变
- 你应该在砖头短缺的情况下做一些更合理的事情，比如还砖清单。
- 范围不需要第一个参数0
- 使用pop()获取和删除元素
- 使用+=进行添加和赋值
- 将枚举与min一起使用，这样您就可以一次获得min的索引
- 不要在函数内部自动打印结果，让用户决定
Code Review用户
发布于 2014-12-20 06:49:45
虽然我之前的回答主要是Python清理，但我相信这也是算法上的改进。请注意，它需要一个(公共的)第三方库，blist，您可以通过pip获得它。
from blist import sortedlist
def tower_greed_sort(bricks, tower_count):
''' Return a list of tower_count lists, each [height, [blocks]]
'''
# A copy of bricks, sorted from shortest to tallest
obricks = list(bricks)
obricks.sort()
# The towers: [[height, [block, block, ...]], ...]
# Take the last (tallest) tower_count bricks
towers = sortedlist([b, [b]] for b in obricks[-tower_count:])
# Only runs the algorithm if we have more bricks than towers to build
if len(obricks) > tower_count:
# Iterate through the rest of the bricks
for brick in obricks[:-tower_count]:
# Here we know that the first tower is the shortest. Remove it for now.
shortest = towers.pop(0)
shortest[0] += brick
shortest[1].append(brick)
''' Instead of doing an O(n) min search through the heights, or even an
O(nlogn) full sort of the towers by height, we do a blist sorted
insert of the modified tower: O(log**2 n).
See http://stutzbachenterprises.com/blist/sortedlist.html
'''
towers.add(shortest)
return towers
bricks = (8, 8, 8, 6, 6, 4, 4, 4, 4, 3, 3, 2)
print(tower_greed_sort(bricks, 5))页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/74206
复制相关文章
相似问题
腾讯云开发者
