具有约束和多个输入的子集求和问题

Question

我正在尝试找出一种方法来实现 python 子集求和问题，其约束条件是必须始终包含 Fixed 变量中的数字。

例如：给定以下列表：

变量 = [1,2,3,4,5]

固定=[6,7]

目标 = [20]

我需要知道 Variable 中的哪个数字组合最接近目标 20（但不超过它），同时 Fixed 列表中的数字必须始终包含在总和中。

Variable 中值的任意组合 + Fixed 中最接近 Target 的所有值

如果有多个组合与目标完全匹配或非常接近（具有相同的值），那么我只看第一个符合条件的组合就可以了。

在上面的例子中，解决方案应该是 6+7+3+4 = 20

我已经尝试了下面的示例，它应该是 return 3，但我得到了 None。诚然，我是 python 的新手，非常感谢任何对我哪里出错的解释。

import pandas as pd

Fixed = pd.Series([3,2])
Variable = pd.Series([15,1,4,6,3,10])
Target = 8


def subsetsum(Variable,Target,Fixed):

    if Target == 0 or Target < 1:
        return None
    elif len(Variable) == 0:
        return None
    else:
        if Variable.iloc[0] == Target:
            return [Variable.iloc[0]]
        else:
            with_v = subsetsum(Variable.iloc[1:], (Target - (Variable.iloc[0]+Fixed.sum())),Fixed)
            if with_v:
                return [Variable.iloc[0]] + with_v
            else:
                return subsetsum(Variable.iloc[1:],Target,Fixed)

Answer 1

这里有一个不使用 pandas 的解决方案，它在这里对你没有任何帮助：

import itertools

Fixed = [3,2]
Variable = [15,1,4,6,3,10]
Target = 8

def findAllSubsets( array, target ):
    answers = []
    for i in range(len(array)):
        for subset in itertools.combinations(array,i+1):
            if sum(subset) == target:
                answers.append( subset )
    return answers

print(findAllSubsets( Variable, Target-sum(Fixed)))

输出是 [3]，这是您的输入集的唯一答案。

具有约束和多个输入的子集求和问题

Subset Sum Problem with constraints and multiple inputs

python

constraints

subset-sum