0

我的任务是解决分级丢番图问题。麦当劳以 6、9 或 20 个 McNuggets 的包装出售麦乐鸡块。因此，例如，可以恰好购买 15 个 McNuggets（一包 6 和一包 9），但不可能正好购买 16 个 nuggets，因为没有 6's、9's 和20 的加起来等于 16。要确定是否有可能恰好购买 n 个 McNuggets，必须求解丢番图方程：找到 a、b 和 c 的非负整数值，这样

6a + 9b + 20c = n。

编写一个函数 buy_nuggets()，它接受一个数字 (n) 作为参数并返回四个数字的元组；销售n个金块所需的包总数、6块块的包数、9块块的包数和20块块的包数。如果无法进行块组合，则返回四个零的元组，即 (0,0,0,0)。

请注意，对于给定的 n，可以有多个解决方案，那么您的解决方案应确保在使用较大的包之前使用较小的包。例如，buy_nuggets(18) 应该返回 (3,3,0,0) 而不是 (2,0,2,0)，即 3 盒 6 块金块超过 2 盒 9 块。输入格式整数 (n)

我得到了限制 -10^6<=a,b,c,n<=10^6

输出格式

4 个数字的元组 (d,a,b,c) 其中

d = 包裹总数 a - 6 个包裹数量 b - 9 个包裹数量 c - 20 个包裹数量

然后我尝试

def nugget_boxes(n): 
    # Write your code here- (above this was given)
    def diophantine(a,b,c,d):
        if a>b and c and d:
            q=extended_nuggets(a,b,c,d)
            a1=q[1]
            b1=q[2]
            c1=q[3]
            d1=q[4]
        if b>a and c and d:
            q=extended_nuggets(a,b,c,d)
            a1=q[2]
            b1=q[1]
            c1=q[3]
            d1=q[4]
        if c>a and b and d:
            q=extended_nuggets(a,b,c,d)
            a1=q[3]
            b1=q[1]
            c1=q[2]
            d1=q[4]           
        else:
            q=extended_nuggets(a,b,c,d)
            a1=q[4]
            b1=q[1]
            c1=q[2]
            d1=q[3]
            assert c%q[0]==0
            d=q[0]
            p=c/d
                return diophantine(int(p*x1),int(p*y1), int(p*z1))
    
    
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(raw_input().strip())

    results = nugget_boxes(n)

    fptr.write(str(results) + '\n')

    fptr.close()

我之前确实问过，并被建议返回函数，我被提到了一个我很感激的 python 教程，我正在阅读，非常简洁但内容丰富。但是，这个特定的问题一直让我很难过。我知道这可能是一项艰巨的任务，但我希望即使以我目前的编码知识，你仍然可以尝试教学。

4

2 回答 2

1

目前尚不清楚您的代码遇到了什么问题，尽管它确实包含几个错误，例如a>b and c and d一个表达式可能并不意味着您认为它的含义。它的意思是'如果a大于b，布尔值c是' True，布尔值d是True'——你可能想要像'ifa大于b，，c和d'这样的东西，尽管从这一点来看，这也没有太大意义算法的观点

问题本身有点奇怪——谁会想要尽可能多的小盒子，因为大盒子通常会给你折扣。但显然，如果这是要求 - 客户永远是对的。

如果允许递归实现（显然是这样），问题就相当简单了：

from typing import Tuple


def pack_nuggets(n: int, sizes: Tuple[int]) -> Tuple[int]:
    if n == 0:
        return (0, *(0 for _ in sizes))
    if not sizes:
        return (0,)
    for x in range(n // sizes[0], 0, -1):
        total, *rest = pack_nuggets((remainder := n - x * sizes[0]), sizes[1:])
        if sum(rest) or not remainder:
            return (sum(rest) + x, x, *rest)
    return (0, *(0 for _ in sizes))


print(pack_nuggets(0, (6, 9, 20)))   # (0, 0, 0, 0)
print(pack_nuggets(10, tuple()))     # (0, )
print(pack_nuggets(18, (6, 9, 20)))  # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20)))  # (5, 3, 1, 1)

编辑：用户@paxdiablo 正确指出解决方案是在 a 中返回一对 anint和tuplea tuple；从风格的角度来看，我更喜欢，但不符合 OP 的问题。新解决方案正确返回单个元组。

如果打字的东西不起作用，您可以使用它 - 但是，这可能意味着您使用的是旧版本的 Python，在这种情况下，海象运算符也可能不起作用。这是适用于较旧 Python 3 版本的解决方案：

def pack_nuggets(n, sizes):
    if n == 0:
        return (0, *(0 for _ in sizes))
    if not sizes:
        return (0,)
    for x in range(n // sizes[0], 0, -1):
        remainder = n - x * sizes[0]
        total, *rest = pack_nuggets(remainder, sizes[1:])
        if sum(rest) or not remainder:
            return (sum(rest) + x, x, *rest)
    return (0, *(0 for _ in sizes))


print(pack_nuggets(0, (6, 9, 20)))   # (0, 0, 0, 0)
print(pack_nuggets(10, tuple()))     # (0, )
print(pack_nuggets(18, (6, 9, 20)))  # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20)))  # (5, 3, 1, 1)
于 2022-02-19T01:00:57.893 回答
0

下面是一个适用于特定盒子大小的迭代解决方案。if通过简单地添加更多嵌套块，它可以扩展到其他盒子场景。

满足“更喜欢小盒子”要求的方法就是确保我们适当地搜索解决方案空间。换句话说，我们从最大可能的六框数开始向下搜索。

类似地，我们从最大可能的九个盒子数量（给定六盒子的数量）开始并向下搜索。

我们不必搜索 20 箱的数量，因为考虑到两个较小尺寸的数量，只有一种可能性：尽可能接近所需数量而不会超过的数量。

然后，如果我们得到了准确的数量，我们会立即返回解决方案。否则，我们继续寻找。如果在穷举搜索后没有找到解决方案，我们返回哨兵值（全为零）。

这肯定比测试每个可能的计数场景并保存满足“首选小盒子”要求的天真方法要好。

import typing as typ

def pack_nuggets(quant: int) -> typ.Tuple[int]:
    """ Figure out how many nugget boxes are needed.

        Given quantity of nuggets, calculates the best triplet
        of boxes (of zize 6, 9, and 20) to satisfy the order.

        Best in this case prefers smaller boxes to larger.

        If no solution, give all zeros.

        Args:
            quant: the quantity of nuggets desired.
        Returns:
            Tuple with total box count followed by count of
            each box in ascending size).
    """

    # Start with maximum possible quantity of six-boxes
    # and gradually reduce to zero.

    max_sixes: int = quant // 6
    for six in range(quant // 6, -1, -1):
        # Start with maximum possible quantity of nine-boxes
        # given current six-box count and gradually reduce
        # to zero.

        six_val: int = six * 6
        max_nines_for_six: int = (quant - six_val) // 9
        for nine in range(max_nines_for_six, -1, -1):
            # There's only really one possible twenty-boxes
            # count that can get to (or a little below) the
            # desired quantity.

            nine_val: int = nine * 9
            twenty: int = (quant - six_val - nine_val) // 20

            # If that's a viable solution, return it.

            if six * 6 + nine * 9 + twenty * 20 == quant:
                return (six + nine + twenty, six, nine, twenty)

    # If there were NO viable solutions, let caller know.

    return (0, 0, 0, 0)

什么自尊的开发人员会在没有测试工具的情况下发布代码？“不是我，”帕克斯说 :-)

# Test harness.

if __name__ == "__main__":
    for test_val in range(55):
        print(f"Result is {pack_nuggets(test_val)} for {test_val} nuggets.")
    print(f"Result is {pack_nuggets(1_000_000)} for {1_000_000} nuggets.")

测试工具的输出显示了正在运行的功能（我添加的评论）：

Result is (0, 0, 0, 0) for 0 nuggets.
Result is (0, 0, 0, 0) for 1 nuggets.
Result is (0, 0, 0, 0) for 2 nuggets.
Result is (0, 0, 0, 0) for 3 nuggets.
Result is (0, 0, 0, 0) for 4 nuggets.
Result is (0, 0, 0, 0) for 5 nuggets.
Result is (1, 1, 0, 0) for 6 nuggets.  # Six is first to satisfy.
Result is (0, 0, 0, 0) for 7 nuggets.
Result is (0, 0, 0, 0) for 8 nuggets.
Result is (1, 0, 1, 0) for 9 nuggets.  # Then nine.
Result is (0, 0, 0, 0) for 10 nuggets.
Result is (0, 0, 0, 0) for 11 nuggets.
Result is (2, 2, 0, 0) for 12 nuggets.
Result is (0, 0, 0, 0) for 13 nuggets.
Result is (0, 0, 0, 0) for 14 nuggets.
Result is (2, 1, 1, 0) for 15 nuggets. # A six and a nine.
Result is (0, 0, 0, 0) for 16 nuggets.
Result is (0, 0, 0, 0) for 17 nuggets.
Result is (3, 3, 0, 0) for 18 nuggets. # Prefer 3*six over 2*nine.
Result is (0, 0, 0, 0) for 19 nuggets.
Result is (1, 0, 0, 1) for 20 nuggets. # A single twenty-box.
Result is (3, 2, 1, 0) for 21 nuggets.
Result is (0, 0, 0, 0) for 22 nuggets.
Result is (0, 0, 0, 0) for 23 nuggets.
Result is (4, 4, 0, 0) for 24 nuggets. # Use 4*six, not 2*nine + six.
Result is (0, 0, 0, 0) for 25 nuggets.
Result is (2, 1, 0, 1) for 26 nuggets.
Result is (4, 3, 1, 0) for 27 nuggets.
Result is (0, 0, 0, 0) for 28 nuggets.
Result is (2, 0, 1, 1) for 29 nuggets.
Result is (5, 5, 0, 0) for 30 nuggets.
Result is (0, 0, 0, 0) for 31 nuggets.
Result is (3, 2, 0, 1) for 32 nuggets.
Result is (5, 4, 1, 0) for 33 nuggets.
Result is (0, 0, 0, 0) for 34 nuggets.
Result is (3, 1, 1, 1) for 35 nuggets.
Result is (6, 6, 0, 0) for 36 nuggets.
Result is (0, 0, 0, 0) for 37 nuggets.
Result is (4, 3, 0, 1) for 38 nuggets.
Result is (6, 5, 1, 0) for 39 nuggets.
Result is (2, 0, 0, 2) for 40 nuggets. # Two twenty-boxes.
Result is (4, 2, 1, 1) for 41 nuggets.
Result is (7, 7, 0, 0) for 42 nuggets.
Result is (0, 0, 0, 0) for 43 nuggets.
Result is (5, 4, 0, 1) for 44 nuggets.
Result is (7, 6, 1, 0) for 45 nuggets.
Result is (3, 1, 0, 2) for 46 nuggets.
Result is (5, 3, 1, 1) for 47 nuggets.
Result is (8, 8, 0, 0) for 48 nuggets.
Result is (3, 0, 1, 2) for 49 nuggets.
Result is (6, 5, 0, 1) for 50 nuggets.
Result is (8, 7, 1, 0) for 51 nuggets.
Result is (4, 2, 0, 2) for 52 nuggets.
Result is (6, 4, 1, 1) for 53 nuggets. # 4*six + nine + twenty.
Result is (9, 9, 0, 0) for 54 nuggets. # Prefer 9*six over 6*nine.

# Still very fast, even for a million nuggets.
# But now I feel quite bloated :-)

Result is (166662, 166660, 0, 2) for 1000000 nuggets.
于 2022-02-19T03:02:07.787 回答