砖墙算法

Question

我在SingPath上做这个问题 -

我们想要制作一排长度恰好为目标的砖块.我们有许多小砖(每块1英寸)和大砖(每块5英寸).如果可以通过从给定的砖块中选择来实现目标,则返回True.这比它看起来有点难,可以在没有任何循环的情况下完成.

所以,我写了这个简单的代码,它适用于所有条件,但除了一个 -

def make_bricks(small,big,goal):
    if (small + big * 5) >= goal:
        return True
    else:
        return False

它不适用于这种情况 - make_bricks(2, 4, 13)我的代码返回一个True,但预期的输出是False.

这是有道理的,但不确定如何将其转换为代码.

Answer 1

你的计算错了; 你需要看看是否有一些大小砖可以用于所需的行; 你只是在确定给出的砖块是否能产生至少那么长的一排.

你不能建造一排长度为13的,因为你没有足够的小砖块; 用两块大砖你需要另外3块小砖.

你需要看看你需要多少5块砖,然后在小砖块中添加剩下的砖块.考虑到1块大砖和8块小砖同样可以用作2块大砖和3块小砖!

首先计算需要多少大砖块,但如果你的理想用量少于理想用量,那么你可以得到你所拥有的大砖块的实际价值,然后看看是否可以用小砖块处理剩余的目标:

def make_bricks(small, big, goal):
    big_bricks = min(goal // 5, big)
    remainder = goal - (big_bricks * 5)
    return remainder <= small

//是整数除法,13 // 5是2,所以你最多使用2块大砖.剩下的就是3,但你只有两块小砖,结果是False:

>>> make_bricks(2, 4, 13)
False
>>> make_bricks(3, 4, 13)
True
>>> make_bricks(8, 1, 13)
True