多目标子集和匹配：候选值单次使用的组合查找算法与Python实现

示例数据 #

targets = [-7.51, -0.32, -0.3, -0.9, -2.9, -1.2, -0.6, -1.2, -2.4, -0.96]
candidates = [-0.32, -0.9, -0.6, -1.4, -1.5, -1.8, -1.2, -0.35, -0.96, -2.52, -0.32, -0.6, -3.84, -0.6, -0.3, -0.6, -0.48]

输出示例 #

target_list = [3, 3, 9]
candidate_list = [1, 2, 3, 4, 5]
result = [{3: [3]}, {3: [1, 2]}, {9: [4, 5]}]

约束条件 #

• 目标数组的总和与候选数组的总和完全相等
• 候选数组中的所有元素仅可被使用一次
• 每个目标值可由1个或n个候选值相加组成

问题描述 #

需要为每个目标值匹配对应的候选值组合，部分场景下候选数组可能不存在完全匹配的子集组合。目前已尝试回溯+深度优先搜索的组合算法，该算法在查找单个目标的匹配组合时有效，但批量为一组目标查找匹配组合时效率极低，无法处理复杂数组场景。

现有实现代码仅能处理简单的目标、候选数组，无法适配复杂数组，代码如下：

import copy
import collections
from decimal import Decimal
import json

class CollectionCheck:

    def combinations(self, candidate_list, target_list):
        origin_candidate_list = copy.deepcopy(candidate_list)
        origin_target_list = copy.deepcopy(target_list)

        def combinationFinder(candidates, target):

            def dfs(pos, rest):
                nonlocal sequence
                if rest == 0:
                    ans.append(sequence[:])
                    return
                if pos == len(freq) or abs(rest) < abs(freq[pos][0]):
                    return

                dfs(pos + 1, rest)
                most = int(min(round(Decimal(rest) / Decimal(freq[pos][0]), 0), freq[pos][1]))
                for i in range(1, most + 1):
                    sequence.append(freq[pos][0])
                    dfs(pos + 1, round((rest - i * float(freq[pos][0])), 2))
                sequence = sequence[:-most]

            freq = sorted(collections.Counter(candidates).items(), reverse=True)
            ans = list()
            sequence = list()

            dfs(0, target)
            return ans

        def safe_remove(candidate_list, potential_combination):
            for value in potential_combination:
                if value in candidate_list:
                    candidate_list.remove(value)

        result = []
        target_list.sort(reverse=True)
        for target in target_list:
            potential_combination = combinationFinder(candidate_list, target)
            if potential_combination == []:
                err = {
                    "info": {
                        "Need to find target": str(target),
                        "List of potential candidates": str(candidate_list),
                        "Algorithm search and return": str(potential_combination)
                    },
                    "origin": {
                        "origin_candidate_list": str(origin_candidate_list),
                        "origin_target_list": str(origin_target_list)
                    }
                }
                err = json.dumps(err)
                return None, err
            else:
                result.append({target: potential_combination[0]})
                safe_remove(candidate_list, potential_combination[0])
        return result, None

复杂数组示例 #

target_list = [-3.12, -3.12, -3.12, -30.6, -16.8, -28.0, -28.8, -18.6, -15.0, -21.0, -6.8, -22.8, -12.8, -22.8,
                   -32.0, -28.0, -16.8, -24.8, -10.8, -5.0, -72.8, -23.8, -42.6, -16.8, -22.8, -12.0, -34.8, -22.8,
                   -19.0, -22.8, -9.8, -45.2, -16.0, -23.0, -17.4, -19.6, -22.8, -28.8, -23.8, -13.8, -28.8, -11.0,
                   -24.0, -12.0, -3.0]

candidate_list = [-19.0, -19.0, -4.8, -0.8, -4.8, -4.8, -4.8, -3.12, -33.0, -4.0, -12.0, -4.8, -24.0, -4.0, -4.8,
                      -30.0, -17.0, -12.0, -4.8, -0.8, -12.0, -4.8, -24.0, -5.0, -24.0, -3.12, -3.2, -4.8, -4.0, -11.0,
                      -4.8, -4.8, -20.0, -6.4, -24.0, -4.8, -28.0, -18.0, -4.8, -4.0, -4.0, -19.0, -12.0, -24.0, -9.6,
                      -1.6, -4.8, -30.6, -18.0, -4.8, -12.0, -17.0, -5.0, -42.0, -24.0, -19.0, -6.0, -18.0, -68.0, -4.0,
                      -4.0, -18.0, -12.0, -4.8, -4.8, -4.8, -18.0, -18.0, -0.8, -11.0, -18.0, -3.0, -11.0, -4.8, -13.0,
                      -1.6, -12.0, -3.12, -6.0]

Lingo建模实现 #

目前可通过Lingo求解该问题，核心为0-1整数规划模型，约束包括：a(i,j)为二进制变量，每个候选j仅分配给1个目标i，每个目标i分配的候选和等于目标值，最小化匹配误差平方和，对应建模代码如下：

model:
  sets:
    !row/1..21/:r;
    !col/1..108/:c;
    row/1..10/:r;
    col/1..17/:c;
    !row/1..4/:r;
    !col/1..8/:c;
    link(row, col):a;
  endsets

  data:
    !r = 10, 9, 8, 7;
    !c = 5, 5, 4, 5, 4, 4, 2, 5;
    r = -7.51, -0.32, -0.3, -0.9, -2.9, -1.2, -0.6, -1.2, -2.4, -0.96;
    c = -0.32, -0.9, -0.6, -1.4, -1.5, -1.8, -1.2, -0.35, -0.96, -2.52, -0.32, -0.6, -3.84, -0.6, -0.3, -0.6, -0.48;
    !r = 1915, 1205, 1370, 1110, 35, 1680, 200, 315, 100, 80, 30, 30, 120, 240, 2895, 1175, 1400, 100, 60, 255, 340;
    !c = 30, 300, 30, 210, 120, 70, 60, 50, 200, 35, 30, 35, 30, 540, 175, 120, 140, 90, 60, 70, 300, 360, 30, 35, 120, 300, 30, 540, 60, 80, 240, 30, 200, 35, 25, 150, 180, 180, 80, 120, 80, 30, 60, 60, 800, 60, 240, 340, 120, 35, 200, 35, 100, 180, 30, 80, 100, 30, 60, 25, 35, 60, 30, 25, 30, 30, 30, 35, 70, 70, 180, 70, 200, 35, 90, 25, 30, 25, 160, 180, 540, 120, 80, 1020, 25, 400, 540, 35, 60, 80, 260, 100, 60, 30, 35, 25, 35, 400, 30, 360, 80, 120, 25, 30, 200, 30, 30, 340;
    !r = -19.15, -12.05, -13.7, -11.1, -0.35, -16.8, -2.0, -3.15, -1.0, -0.8, -0.3, -0.3, -1.2, -2.4, -28.95, -11.75, -14.0, -1.0, -0.6, -2.55, -3.4;
    !c = -0.3, -3.0, -0.3, -2.1, -1.2, -0.7, -0.6, -0.5, -2.0, -0.35, -0.3, -0.35, -0.3, -5.4, -1.75, -1.2, -1.4, -0.9, -0.6, -0.7, -3.0, -3.6, -0.3, -0.35, -1.2, -3.0, -0.3, -5.4, -0.6, -0.8, -2.4, -0.3, -2.0, -0.35, -0.25, -1.5, -1.8, -1.8, -0.8, -1.2, -0.8, -0.3, -0.6, -0.6, -8.0, -0.6, -2.4, -3.4, -1.2, -0.35, -2.0, -0.35, -1.0, -1.8, -0.3, -0.8, -1.0, -0.3, -0.6, -0.25, -0.35, -0.6, -0.3, -0.25, -0.3, -0.3, -0.3, -0.35, -0.7, -0.7, -1.8, -0.7, -2.0, -0.35, -0.9, -0.25, -0.3, -0.25, -1.6, -1.8, -5.4, -1.2, -0.8, -10.2, -0.25, -4.0, -5.4, -0.35, -0.6, -0.8, -2.6, -1.0, -0.6, -0.3, -0.35, -0.25, -0.35, -4.0, -0.3, -3.6, -0.8, -1.2, -0.25, -0.3, -2.0, -0.3, -0.3, -3.4;
  enddata
  
  min=@sum(row(i):(r(i)-@sum(col(j):a(i, j)*c(j))) ^ 2);
  
  @for(row(i):@for(col(j):@bin(a(i, j))));
  @for(row(i):@sum(col(j):a(i, j) * c(j)) = r(i));
  @for(col(j):@sum(row(i):a(i, j)) = 1);

end

现寻求用Python实现上述整数规划模型求解的解决方案。

内容的提问来源于stack exchange，提问作者Tony Joy