从数组中选出和为 7 的倍数的子序列的最大和

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-27 12:09:12
    编辑于：2022-03-27 12:09:12
    浏览量：796

概述

回溯法

#include <bits/stdc++.h>
using namespace std;

vector<int> nums;
int ans = 0;

void backtrack(int i, int sum) {
    if (i == nums.size()) {
        if (sum % 7 == 0) {
            ans = max(ans, sum);
        }
        return;
    }
    backtrack(i + 1, sum + nums[i]);
    backtrack(i + 1, sum);
}

int main() {
    int n; cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    backtrack(0, 0);
    cout << ans << endl;
}

分治法

#include <bits/stdc++.h>
using namespace std;

vector<int> nums;

set<int> helper(int i, int j) {
    set<int> res;
    if (i == j) {
        res.insert(0);
        res.insert(nums[i]);
        return res;
    }
    int m = (i + j) / 2;
    auto s1 = helper(i, m);
    auto s2 = helper(m + 1, j);
    for (auto a : s1) {
        for (auto b : s2) {
            res.insert(a + b);
        }
    }
    return res;
}

int main() {
    int n; cin >> n;
    nums.resize(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    auto s = helper(0, n - 1);
    int ans = 0;
    for (auto a : s) {
        if (a % 7 == 0) {
            ans = max(ans, a);
        }
    }
    cout << ans << endl;
}

Links: 从数组中选出和为-7-的倍数的子序列的最大和