python - 在候选中找到总和为目标的所有组合

Question

示例数据：

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]

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

健康）状况：

1. 目标数组之和等于候选数组之和。
2. 候选人数组中的所有元素只能使用一次。
3. 每个目标可能由 1 个或 n 个候选者组成。

问题：是否有一个算法可以让每个目标找到及其在候选数组中的组合？

注意：有时需要考虑候选数组是否不完美才能找到每个目标的子集组合。

我尝试了回溯和深度搜索的组合。这个算法在寻找目标的时候是有效的，但是当需要寻找一个群体目标的时候，这个时候就很难找到了。这个是类似的，我还没有想法。

我是来寻求帮助的。

这是我的代码，它适用于简单的目标和候选数组，但不适用于更复杂的数组。

 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解决问题，但是现在不知道怎么用python代码来实现这个公式。

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

Lingo 截图 0

行话截图 1

标签： pythonalgorithmdynamic-programmingnp-completequadratic-programming