如何解决Java中100+元素数组的最接近子集求和问题？

Question

我最近遇到了一个子集和问题。我之前可以使用 Java 解决较小的数组问题，但在这种情况下，我真的不知道该怎么做。蛮力和重复可能不是一种选择，因为我遇到了内存不足的问题。

所以，假设我们有一个 {2500, 3200, 3300} 的数组。我们正在寻找最接近所需数字 K = 135000 的 总和。主要区别在于我们可以多次使用数组中的数字。

好的，如果我们可以多次使用它们，那么我们可以将其更改为更“传统”的方式——只需将 K 除以这些数字中的每一个——即 54、42 和 40 - 并且 创建一个新数组 ，其中包含从除法中获得的次数。它将是 {2500, 2500, 2500, ... , ... 3300, 3300} 并且新数组的 长度为 136.现在这 比 3.
多得多
那么 - 如何解决最接近的 子集和问题，我们可以从 中选择 超过 2 个数 ]包含 136 个或更多元素的数组 使用 Java?

我想要得到的是不仅是最接近的和，而且给出那个和的元素列表。

我听说过并正在阅读动态规划、逼近算法和遗传算法，但不幸的是我对这些一无所知。前段时间我为一个不同的案例做了遗传算法，但我不知道如何在这个案例中使用它。

有什么想法吗？我很乐意提供帮助。

Answer 1

我不会帮你解决的。但我会用伪代码（又名 Python）为您提供关键思想。

我们从表示以下语句的状态开始：“我不知道如何得出任何数字。我可以生成的 best 是 0。我还没有处理了我可以到达 0."

的事实

在数据中：

can_generate = set()
todo = [0]
best = 0
K = 135000

我们要做的是，当todo中有任何东西时，取一个值，看看它对我们来说是否是新的。如果是，我们可能会更新 best，并可能向 todo 添加新值。像这样：

while len(todo):
    value = todo.pop()
    if value not in can_generate:
        can_generate.add(value)
        if abs(K-value) < abs(K-best):
            best = value
        if value < K:
            for term in [2500, 3200, 3300]:
                todo.append(value + term)

现在我们知道 can_generate 中的值，我们向后搜索以找到如何到达那里。

answer = []
while 0 < best:
    for term in [3300, 3200, 2500]:
        if best - term in can_generate:
            answer.append(term)
            best -= term
            break

如何解决Java中100+元素数组的最接近子集求和问题？

How to solve the closest subset sum problem in Java for 100+ element arrays?

java

algorithm

np-complete