时间戳

首页 > 解决方案 > 通过重复减去某些数字来最小化整数

python - 通过重复减去某些数字来最小化整数

问题描述

我正在尝试用 Python 编写一个程序，该程序接受一个正整数和一个来自用户的正整数列表。然后它应该重复从单个整数中减去列表中的整数，直到没有减法选项留下（单个整数的最终版本应该是正数或零）。最后，它应该返回单个整数末尾的最小值。

例如 -> 16 & [2, 5, 7, 20] -> 返回 0（从 16 中减去 8 乘以 2 或 2 乘以 5 和 3 乘以 2）& 20 & [14, 16, 21] -> 返回 4 (从 20 中减去 16)

没有与所采取的步骤数或我们使用列表中某个元素的时间相关的限制。

我尝试用 scipy.optimize.minimize 和递归编写它，都失败了。

目前，我正在寻找没有库导入的解决方案。

提前感谢您的回答

标签： pythonalgorithmrecursion

解决方案

这是硬币找零问题的一个变体，并且有一个解决方案与该问题的标准解决方案相同。这是一个动态规划问题，它存储从 0 到目标数字的每个值可实现的最小总数，更新每个可以减去的值（硬币）的结果。

它在 O(nm) 中运行，其中 n 是目标数，m 是包含可以减去的值的列表的长度。

def minsub(t, xs):
    n = list(range(t+1))
    for x in xs:
        for i in range(x, t + 1):
            n[i] = min(n[i], n[i - x])
    return n[t]

下面是一些简单的测试：

tests = [
    (16, [2, 5, 7, 20], 0),
    (20, [14, 16, 21], 4)
]
for t, xs, want in tests:
    got = minsub(t, xs)
    print(t, xs, got, want)
    assert got == want

推荐阅读