时间戳

首页 > 解决方案 > 具有约束和多个输入的子集和问题

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

问题描述

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

例如：给定以下列表：

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

固定 = [6,7]

目标 = [20]

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

变量中的值的任意组合 + 固定中最接近目标的所有值

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

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

我已经尝试了下面的示例，它应该返回 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)

标签： pythonconstraintssubset-sum

解决方案

这是一个不使用熊猫的解决方案，在这里对您没有任何帮助：

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]，这是您的输入集的唯一答案。

推荐阅读