"篮子"的最优组合以最接近目标篮子?

Question

假设我有一个长度为n的数组，其中arr[k]表示我想要的对象k的大小。我也有一些任意数量的数组，我可以对它们进行任意组合的整数倍求和——我的目标是最小化每个元素之间的绝对差的总和。

所以作为一个愚蠢的例子，如果我的目标是[2,1]，我的选项是a =[2,3]和B =[0,1]，那么我可以选择a - 2B，成本为0

我想知道是否有一种有效的算法来近似这样的东西?它有一种奇怪的背包的味道也许它只是难以处理大n?它似乎不太适合DP方法

Answer 1

这是(NP-hard)最接近向量问题。Fincke和Pohst提出了一种算法("改进了计算晶格中短长度向量的方法，包括复杂性分析")，但我个人没有使用过它。