满足条件的最大组合

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-19 13:37:01
    编辑于：2022-03-22 21:44:09
    浏览量：602

概述

有一个数组，要你找出最大的组合，使得该组合中元素的和能被 k1 整除但是不能被 k2 整除，问最大值是多少且能达到最大值的组合个数。

回溯法

回溯法暴力遍历所有可能。

根据 JW 反馈超时。

分治

给定一个序列，将其分为两个子序列，每个子序列分别计算自己所有可能的和，并统计出现次数。

虽然也很暴力吧，但是，对于出现的和相同的组合方法，我们只需要和别人组合一次。

写的时候别忘了，当前区间也可以不选择，所以要有 res[0] = 1;

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, int> helper(vector<int> &nums, int l, int r) {
    unordered_map<int, int> res;
    if (l == r) {
        res[0] = 1;
        res[nums[l]] = 1;
        return res;
    }
    int m = (l + r) / 2;
    auto m1 = helper(nums, l, m);
    auto m2 = helper(nums, m + 1, r);
    for (auto &iter1: m1) {
        for (auto &iter2: m2) {
            res[iter1.first + iter2.first] += iter1.second * iter2.second;
        }
    }
//    cout << "l " << l << " r " << r << " -> ";
//    for (auto & iter : res) {
//        cout << iter.first << " ";
//    }
//    cout << endl;

    return res;
}

int main() {
    int n, k1, k2;
    cin >> n >> k1 >> k2;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    auto ans = helper(nums, 0, n - 1);
    int res = 0;
    int count = 0;
    for (auto &iter: ans) {
        if (iter.first % k1 == 0 && iter.first % k2 != 0) {
            if (iter.first > res) {
                res = iter.first;
                count = iter.second;
            }
            res = max(res, iter.first);
        }
    }
    cout << res << " " << count;
}

测试：

输入：
10 4 6
0 1 2 3 4 5 6 7 8 9

输出：44 8

Links: 满足条件的最大组合