其他解决方案似乎是从精确求和向后工作的

拟合盒数的计算算法

不完全是零钱硬币的问题

其他人说子集和问题的变体

天真的伪思维在当下解决问题：

获取每个的倍数
逐步递增所有元素组合的和(/元素倍数的组合；不确定最佳方法(
当每个求和器超过给定数字(阈值(时停止
mod以比较经过给定数的最小余数i.可能不需要此步骤，具体取决于组合是如何一起/单独构建的
找到总和

认为这个或其他明显的python示例可能有数学解决方案

https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/

其和是特定阈值上最小和的子集——我认为这种动态编程非常类似于这里的挑战；然而，我在如何以务实的方式逐步组合/乘以(+记忆(所有元素的潜在组合方面遇到了一些障碍。

递归减法在这类问题中效果好吗？

示例测试用例

用任意数5设置[1, 4, 4.5]；最小和=5(4+1(
用任意数5.1设置[1, 4, 4.5]；最小和=5.5(4.5+1(
将[20, 40, 9001]设置为任意数88；最小和=100(40+40+20或20+20+20+20+20等(
用任意数145设置[20, 40, 9001]；最小和=160(40+40+40+40或20+20+20+20+20+20+20+20+20等(
用任意数9000设置[20, 40, 9001]；最小和=9000(我想是40*225等(
用任意数9001设置[20, 40, 9001]；最小和=9001(9001，举例说明具有奇怪的不可分割分量的情况，给定任意集(
用任意数18002设置[20, 40, 9001]；最小和=18002(9001+9001(
用任意数101设置[100, 300, 420]；最小和=200(100+100(
用任意数398.001设置[100, 300, 420]；最小和=400(300+100(
用任意数404设置[100, 300, 420]；最小和=420(420(

感谢您提供任何额外的上下文、指针或简单的伪代码解决方案。

这本身可能不是一个算法，但您可以使用混合整数编程来解决这个问题。以下是在Python中使用PuLP的示例：

import pulp
def solve(lst, target):
# define a minimization problem
prob = pulp.LpProblem("CombProb", pulp.LpMinimize)
# vars[i] counts the number of time lst[i] is used in an optimal solution
vars = pulp.LpVariable.dicts("count",  range(len(lst)), lowBound=0, cat="Integer")
# define the objective
prob += sum(vars[i] * lst[i] for i in range(len(lst)))
# define the constraint
prob += sum(vars[i] * lst[i] for i in range(len(lst))) >= target
# solve the problem and check termination status
assert prob.solve() == 1
# return the objective value and involved list elements
return prob.objective.value(), {lst[i]: vars[i].varValue for i in range(len(lst))}
tests = [
#   (lst, target, solution)
([1, 4, 4.5], 5, 5),
([1, 4, 4.5], 5.1, 5.5),
([20, 40, 9001], 88, 100), 
([20, 40, 9001], 145, 100),
([20, 40, 9001], 9000, 9000),
([20, 40, 9001], 9001, 9001),
([20, 40, 9001], 18002, 18002),
([100, 300, 420], 101, 200),
([100, 300, 420], 398.001, 400),
([100, 300, 420], 404, 420),
]
for i, (lst, target, sol) in enumerate(tests, start=1):
res = solve(lst, target)[0]
if res == sol:
continue
else:
print(f"Error in case {i} with expected solution {sol} and computed solution {res}")

测试用例4中似乎有一个错误，但其他测试用例都通过了

我根本没有考虑效率，但一个天真的实现似乎很简单：

const {ceil, min} = Math;
const range = (lo, hi) => [... Array (hi - lo + 1)] .map ((_, i) => i + lo);
const minMult = ([n, ...ns], t) => 
ns .length == 0 
? n * ceil (t / n)
: min ( ...range (0, ceil (t / n)) .map (k => k * n + minMult (ns, t - k * n)));
[
[[1, 4, 4.5], 5],
[[1, 4, 4.5], 5.1],
[[20, 40, 9001], 88],
[[20, 40, 9001], 145],
[[20, 40, 9001], 9000],
[[20, 40, 9001], 9001],
[[20, 40, 9001], 18002],
[[100, 300, 420], 101],
[[100, 300, 420], 398.001],
[[100, 300, 420], 404]
] .forEach (
([ns, t]) => console .log (`minMult ([${ns.join(', ')}], ${t}) //=> ${minMult(ns, t)}`)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

我们重复数组的长度。当我们只有一个数字时，答案只是这个数字的最小倍数，不大于目标。否则，我们将第一个数字的每个倍数向上乘以不大于目标的最小倍数，然后在剩余数字和原始数字的未覆盖部分上重复，将结果相加。

JS没有range函数，所以我们必须包含自己的函数。这个版本比Pythons更简单，不提供step参数，并且包括最后一个值，而不是在它之前停止

算法计算一个数字的最小和

备选措辞：

其他解决方案似乎是从精确求和向后工作的

天真的伪思维在当下解决问题：

示例测试用例

相关内容

最新更新

热门标签：