解丢番图

Question

我的任务是解决渐变丢番图问题。麦当劳以6、9或20 McNuggets的包装出售鸡肉McNuggets。例如，可以买到15 McNuggets (一包6，一包9)，但不可能买到整整16个金块，因为没有6，9和20的非负整数组合等于16。要确定是否可以买到确切的n McNuggets，必须求解一个丢番图方程:求a、b和c的非负整数值，这样就可以确定是否可以买到n个McNuggets。

6a + 9b + 20c = n。

编写一个函数buy_nuggets()，该函数以一个数字(n)作为参数，并返回四个数字的元组:包总数、6个块的包数、9个块的包数和出售n个块所需的20个块包的数量。如果无法进行金块组合，则返回四个零的元组，即(0，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-6b包装件数9c包装件数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教程，我很感激，我正在阅读，非常简洁，但内容丰富。然而，这个具体的问题给了我一段艰难的时光。我知道这可能是一项艰巨的任务，但我希望你仍然可以尝试教学，即使我目前的编码知识。

Answer 1

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

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

同样，我们从最大可能的九盒数(给定六盒的数目)开始，然后向下搜索。

我们不需要搜索二十个盒子的数量，因为，考虑到两个较小的大小的数量，只有一种可能性:尽可能接近所需数量而不经过检查的数字。

然后，如果我们得到了准确的数量，我们立即返回解。否则我们就继续搜索。如果在穷尽搜索后找不到解决方案，则返回哨兵值(全部为零)。

这肯定比天真的方法更好，即测试每一种可能的计数方案，并保存满足“更小的盒子”要求的方案。

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.

Answer 2

目前还不清楚您的代码遇到了什么问题，尽管它确实包含了几个错误，比如a>b and c and d是一个表达式，可能并不意味着您认为它会做什么。它的意思是‘如果a大于b，c的布尔值是True，而d的布尔值是True’--您可能想要‘如果a大于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)

编辑: user @ pair正确地指出，解决方案是在tuple中返回一对tuple和一个tuple；从风格的角度来看，我更喜欢这一点，但与OP的问题不一致。新解决方案正确地返回单个元组。

如果输入内容不起作用，您可以使用它--但是，这可能意味着您使用的是Python的旧版本，在这种情况下，walrus操作符也可能无法工作。下面是一个适用于早期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)