算法计算一个数适合的最小和

Question

给定一组数，找出任意数适合的最小倍数和

< li >集合中的数字可以多次使用(或根本不使用)以获得“总和” < li >这组数字可以是任何正十进制数(即< code>1，4，4.5 ) < li >给定/任意数阈值可以是任意小数(即< code>5 )

> < li>

找出给定数字能与最小余数相适应的倍数组合

找到一个数字可以四舍五入到的最小“总和”

每个组合中使用的实际数字本身对于这个特定的挑战并不重要

• 虽然这可能很有趣，但锻炼也^

目标是找到最小的“总和”(精确的或四舍五入的总和)；然而，我很乐意探索/了解其他因素

试衣盒数量计算算法

• 不完全是零钱硬币问题

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

1. 获取每个的倍数
2. 逐步递增所有元素的组合总和（/元素的倍数的组合，不确定执行此操作的最佳方法）
3. 当每个求和器超过给定数字（阈值）时停止
4. 用于比较已超过给定数字的最小余数的mod i.可能不需要此步骤，具体取决于组合如何构建在一起/单独构建
5. 找到总和

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

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

其总和是特定阈值上的最小总和的子集——我认为这个动态规划非常类似于这里的挑战；然而，对于如何以一种实用的方式逐步组合/倍增(记忆)所有元素的潜在组合，我遇到了一点障碍。

递归向后减法在这类问题中有效吗？

1. 用任意数字设置[1，4，4.5]；最小和=5（41）
2. 用任意数字设置[1，4，4.5]；最小和=5.5（4.51）
3. 用任意数字设置[20，40，9001]；最小总和=100（40 40 20或20 20 20 20，等等）
4. 用任意数字设置[20，40，9001]；最小总和=160
5. 用任意数字设置[20，40，9001]；最小总和=9000（我想是40*225等）
6. 用任意数字设置[20，40，9001]9001；最小和=9001
7. 用任意数字设置[20，40，9001]1800218002（9001 9001）
8. 用任意数字设置[100，300，420]101200（100 100）
9. 用任意数字设置[100，300，420]398.001400（300 100）
10. 用任意数字设置[100，300，420]；最小和=<代码>420 （420）

感谢您提供您可以帮助的任何其他上下文、指针或简单的伪代码解决方案。




Answer 1

我根本没有考虑过效率问题，但一个简单的实现似乎很容易编写：

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}

Answer 2

这可能不是算法本身，但您可以使用混合整数规划来解决此问题。下面是在蟒蛇中使用 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中似乎有一个错误，但是其他测试用例通过了。