达到给定数值的最小步数

Question

我需要通过加/减一系列值l到n来计算从值n到值x的最小方法数

例如：值n=100，值X=45 列表，l，：50,6,1

最好的办法是说： 100-50-6+1=45

我想要一个程序来计算给定列表，l中x和n的任何值

我真的很难勾勒出我将如何写这篇文章。你知道吗

我对如何克服以下问题感到困惑：

• 如果我尝试添加或删除，如何通知程序 减法以及应该做多少次。例如我 可能需要先减，再加，再减才能得到一个 解决方案
• 如何包含足够的for/while循环以确保提供 所有可能输入值的解决方案

以前有没有人遇到过这样的问题，有没有人知道我如何为这样一个解决方案概述代码（如果Python能帮助我学习一些可以帮助我的特定函数，那么我正在使用Python）

谢谢

这是我迄今为止的尝试，但我被卡住了

inputA = ""
while inputA == "":
    inputA = input("""Please enter two numbers, separated by a comma.
                The first value should indicate the number of jugs:

                The second value should indicate the volume to be measured

                """)

itemList = list(inputA.split(","))
valueToMeasure = int(itemList[1])

inputB = ""

while inputB == "":
    inputB = input("Plese enter the volumes for the {} jug(s) listed: ".format((itemList[0])))

    if len(inputB.split(",")) != int(itemList[0]):
        inputB = ""

TargetVolume = itemList[1]
jugSizes = inputB.split(",")

print("Calculating: smallest number of steps to get", TargetVolume, "ml using jugs of sizes:", jugSizes)


jugSizes.sort()
jugSizes.reverse()
largestJug = int(jugSizes[0])

ratioTable = {}
for item in jugSizes:
    firstVal = int(jugSizes[0])

    itemV = int(item)
    valueToAssign = firstVal/itemV

    ratioTable[int(item)] = int(valueToAssign)

taskPossible = True

if valueToMeasure > largestJug:
    print ("Impossible task")
    taskPossible = False

newList = jugSizes
if taskPossible == True:
    for item in jugSizes:
        if item < TargetVolume: break
        newList = newList[1:]
        newDict  = {}
        for itemA in ratioTable:
            if int(itemA) < int(item):
                newDict[itemA]= ratioTable[itemA]
        print ("Do work with these numbers:", newDict)

Answer 1

如果我理解正确，这就是我解决问题的方法。你知道吗

X = 45
largest_jug = measured = 100
jug_sizes = [50, 6, 1]
steps = []
jug_to_use = 0

while measured != X:
    if jug_to_use < len(jug_sizes) - 1: # we have smaller jugs in reserve
        error_with_large_jug = min([abs(measured - jug_sizes[jug_to_use] - X), abs(measured + jug_sizes[jug_to_use] - X)])
        error_with_small_jug = min([abs(measured - jug_sizes[jug_to_use + 1] - X), abs(measured + jug_sizes[jug_to_use + 1] - X)])
        if error_with_small_jug < error_with_large_jug:
            jug_to_use += 1
    if measured > X:
        measured -= jug_sizes[jug_to_use]
        steps.append(('-', jug_sizes[jug_to_use]))
    else:
        measured += jug_sizes[jug_to_use]
        steps.append(('+', jug_sizes[jug_to_use]))
print(steps)

屈服

[('-', 50), ('-', 6), ('+', 1)]

它基本上从使用最大的罐子开始，直到它在下一个尺寸的范围内，以此类推。我们可以用随机大小的[30, 7, 1]罐子来测试它，再次看到它的结果是[('-', 30), ('-', 30), ('+', 7), ('-', 1), ('-', 1)]。你知道吗

重要提示：

• jug_sizes应该从大到小排序
• 这个解决方案假设X可以用jug_sizes中提供的数字来达到（否则它将无限循环）
• 这并没有考虑到jug大小会使目标无法访问（即[50, 12, 5]，其中12个大小应该跳过，否则解决方案无法访问）
• 这假设每个罐子都应该使用（与上述点相关）

不过，我相信你可以根据自己的具体情况找出解决这些问题的办法