搜索剪枝

2021-10-10 | 阅读：次

===

Index

子集和问题

子集和问题

子集和问题 是从一个集合中选出一部分子集，使得这个子集的和满足一定条件，子集和问题有很多种变种，不同变种和数据范围采用的方法也不尽相同。

部分子集和

判断能否从数组a中选择一个子集，其和为s.

设 sum(a) = n, n <= 1e5时，可以使用 bitset，判断所有子集能构成和的可能。

时间复杂度 O(n*sqrt(n)/w) w = 32或64，取决于机器。

template<size_t n>
bitset<n + 1> partial_sum(vector<int> &a) {
    int s = accumulate(a.begin(), a.end(), 0ll);
    assert(s <= n);
    vector<int> cnt(s + 1);
    for (int x : a) {
        cnt[x] ++;
    }
    for (int i = 1; i * 2 <= s; ++i) {
        int num = (cnt[i] - 1) / 2;
        cnt[i] -= num * 2;
        cnt[i * 2] += num;
    }
    bitset<n + 1> dp;
    dp[0] = 1;
    for (int i = 1; i <= s; ++i) 
        for (int t = 0; t < cnt[i]; ++t) 
            dp |= dp << i;
    return dp;
}

使用示例:

vector<int> a;
auto dp = partial_sum<100000>(a);
dp.test(s); //

分割等和子集

leetcode 416

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100 数组的大小不会超过 200

分析

数据值范围较小，可以直接转化为01背包问题
从数组中选取一部分数，能否使得背包容量恰好为s / 2。

    bool canPartition(vector<int>& nums) {
        int s = 0;
        for (auto x : nums) s += x;
        if (s & 1) return false;
        vector<int> dp(s / 2 + 1);
        dp[0] = 1;
        for (auto x : nums) {
            for (int i = dp.size() - 1; i >= x; --i) {
                if (dp[i - x]) dp[i] = 1;
            }
        }
        return dp.back() == 1;
    }

数组分割

有一个没有排序，元素个数为2n的 正整数 数组，把这个数组分为元素个数为n的两个数组，使两个子数组的和最接近。

数组元素之和 sum 比较小时

转化为背包问题，从2n件物品中取n件物品，总合不超过sum的最大值是多少。

    int solve(vector<int>& nums) {
        int sum = 0, n = nums.size()/2;
        for(auto& x: nums) sum += x;
        vector<vector<int>> dp(n+1,vector<int>(sum/2+2));
        for (int i = 1; i <= 2 * n; ++i) {
            for(int j = 1; j <= min(i,n); ++j) {
                for (int s = sum/2+1; s >= nums[i-1]; --s) {
                    dp[j][s] = max(dp[j-1][s-nums[i-1]]+nums[i-1], dp[j][s]);
                }
            }
        }
        return dp[n][sum/2+1];
    }

或者打表，dp[i][v] 表示是否能从数组中找到i个数，使其和为v。

    int solve(vector<int> nums){
        int sum = 0, n = nums.size()/2;
        for(auto& x: nums) sum += x;
        vector<vector<int>> dp(n+1,vector<int>(sum/2+2));
        for (int i = 1; i <= 2 * n; ++i) {
            for(int j = 1; j <= min(i,n); ++j) {
                for (int s = sum/2+1; s >= nums[i-1]; --s) {
                    if (dp[j-1][s-nums[i-1]]) dp[j][s] = 1;
                }
            }
        }
        for (int s = sum/2; ~s; --s) {
            if (dp[n][s]) return s;
        }
        return 0;
    }

子集和优化

有N个物品，第i个物品有权重wi, wi<=D, 能否从数组中选出一个子集，使得子集中的元素和为C.

在N，D不大时，可以通过 O(ND)算法求解这个问题。

相关题目

kickstart 2022roundc P2

atcoder abc221 G

/*
从数组a中选出一个子集，和为t。
如果不存在，返回{}，
否则返回长度为n的数组ans,ans[i]=1表示选择a[i],为0表示不选择a[i].
*/
vector<bool> subset_sum(const vector<int> &a, int t) {
    int n = a.size(), mx = *max_element(a.begin(), a.end());
    int x = 0, s = 0;
    while (x < n && s + a[x] <= t) s += a[x++];
    if (x == n && s != t) return {};
    vector<int> dp(mx * 2, -1);
    vector p(n, vector<int>(mx * 2, -1));
    int offset = t - mx + 1;
    dp[s - offset] = x;
    for (int i = x; i < n; ++i) {
        vector<int> dp2 = dp;
        for (int j = mx - 1; j >= 0; --j) {
            if (dp2[j + a[i]] < dp2[j]) {
                p[i][j + a[i]] = -2;
                dp2[j + a[i]] = dp2[j];
            }
        }
        for (int j = mx*2 - 1; j >= mx; --j) {
            for (int k = dp2[j] - 1; k >= max(dp[j], 0); k--) {
                if (dp2[j - a[k]] < k) {
                    p[i][j - a[k]] = k;
                    dp2[j - a[k]] = k;
                }
            }
        }
        swap(dp, dp2);
    }
    if (dp[mx - 1] == -1) return {};

    vector<bool> ans(n);
    int i = n - 1, j = mx - 1;
    while (i >= x) {
        int c = p[i][j];
        if (c == -2) {
            ans[i] = !ans[i];
            j -= a[i];i--;
        } else if (c == -1) i--;
        else {
            ans[c] = !ans[c];
            j += a[c];
        }
    }
    while (i >= 0) {
        ans[i] = !ans[i];
        i--;
    }
    return ans;
}

送礼物

acwing 171

有N个礼物，第i个礼物重量为G[i], 从N个礼物中选出一部分礼物，其重量和不超过w，且重量和最大。

数据范围

1 <= N <= 46
1 <= w,G[i] <= 2^32 - 1

分析

这题n比较小，但是重量很大，如果用背包问题，时间复杂度 n*sum 会超时。这题n比较小，可以用搜索。但是n=46，直接搜索时间复杂度 2^n会超时，这时我们可以使用双向搜索的思想，把礼物分成两半。

先搜索前N/2个物品可以凑出来的所有重量，存到数组中
对所有重量排序，判重
再搜索后一半物品可以凑出来的所有重量，假如当前重量为，则可以在预处理初的所有重量中二分出一个，使得x+y<=w,且x+y最大。

双向dfs实现，使用静态数组，用set会超时

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


int w, n, k, cnt = 0;
ll ans = 0;

const int N = 1<<25;
int st[N];

ll g[50];
void dfs(int u, ll s) {
    if(u == k) { //已经枚举完第k个数，就把当前的s驾到weights中
        st[cnt++] = s; // 用数组模拟set, 直接用set会超时。
        return;
    }
    dfs(u+1, s); // 不选这个物品
    if(s + g[u] <= w)  // 选这个物品
        dfs(u+1, s + g[u]);
}
void dfs2(int u, ll s){
    if(u == n) { // 已经找完了n个物品
    
        int p = upper_bound(st, st + cnt, w - s) - st;
        if (p == 0) ans = max(ans,s);
        else  ans = max(ans, s + st[p-1]);
        return;
    }
    dfs2(u+1, s);
    if(s + g[u] <= w) 
        dfs2(u+1,s + g[u]);
}
int main()
{
    cin>>w>>n;
    for (int i = 0; i < n; i ++ ) cin>>g[i];
    sort(g,g+n,greater<int>()); //从大到小搜索，优化搜索顺序
    k = n / 2 + 2;
    dfs(0, 0);
    sort(st, st+cnt);
    int t = 1; // 去重
    for (int i = 1; i < cnt; ++i) 
        if (st[i] != st[i-1]) st[t++] = st[i];
    cnt = t;
    dfs2(k, 0);
    cout << ans << endl;
    
}

二进制实现

二进制枚举比dfs慢n倍，这里会超时。

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


int w, n, k, cnt = 0;
ll ans = 0;

const int N = 1<<25;
ll st[N];

int g[50];

int main()
{
    cin>>w>>n;
    for (int i = 0; i < n; i ++ ) cin>>g[i];
    sort(g,g+n,greater<int>()); //从大到小搜索，优化搜索顺序
    k = n / 2 + 2;
    
    for(int i=0;i<1<<k;++i) {
        ll s=0;
        for(int j=0;j<k;++j){
            if((i>>j)&1) {
                s+=g[j];
                if(s>w) break;
            }
        }
        if(s<=w) st[cnt++]=s;
    }

    sort(st, st+cnt);
    int t = 1; // 去重
    for (int i = 1; i < cnt; ++i) 
        if (st[i] != st[i-1]) st[t++] = st[i];
    cnt = t;
    for(int i=0;i<1<<(n-k);++i){
        ll s=0;
        for(int j=0;j<n-k;++j){
            if((i>>j)&1) {
                s+=g[j+k];
                if(s>w) break;
            }
        }
        if(s<=w) {
            int p=upper_bound(st,st+cnt,w-s) - st;
            if(p==0) ans = max(ans,s);
            else ans = max(ans, s + st[p-1]);
        }
    }
    cout << ans << endl;
    
}

最接近目标值的子序列和

leetcode 1755（周赛227）

给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要最小化绝对差 abs(sum - goal) 。

返回 abs(sum - goal) 可能的最小值。

注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

数据范围

1 <= nums.size() <= 40
1e7 <= nums[i] <= 1e7
-1e9 <= goal <= 1e9

双向dfs解法

int n, s, w, cnt = 0, k, ans;
const int N = 1 << 23;
int st[N];
vector<int> g;
class Solution {
public:
    void dfs1(int u, int s){
        if(u == k) {
            st[cnt++] = s;
            return;
        }
        dfs1(u+1, s); 
        dfs1(u+1, s + g[u]);
    }
    void dfs2(int u, int s){
        if(u == n) {
            int p = upper_bound(st,st+cnt, w-s) - st;
            if(p != cnt) ans = min(ans, abs(st[p]+s-w));
            if(p != 0) ans = min(ans, abs(st[p-1]+s-w));
            return;
        }
        dfs2(u+1, s); 
        dfs2(u+1, s + g[u]);
    }
    int minAbsDifference(vector<int>& nums, int goal) {
        n = nums.size(), w = goal, ans = abs(goal), cnt = 0, k = n/2;
        g = nums;
        dfs1(0, 0);
        sort(st, st+cnt);
        int t=1;
        for(int i=1;i<cnt;++i) {
            if(st[i]!=st[i-1]) st[t++]=st[i];
        }
        dfs2(k,0);
        return ans;
    }
};

二进制枚举

const int N = 1 << 23;
int st[N];
class Solution {
public:
    int minAbsDifference(vector<int>& g, int w) {
        int n = g.size(), ans = abs(w), cnt = 0, k = n/2;
        for(int i=0;i<1<<k;++i){
            int s=0;
            for(int j=0;j<k;++j){
                if(i>>j&1) s+=g[j];
            }
            st[cnt++] = s;
        }
        sort(st, st+cnt);
        int t=1;
        for(int i=1;i<cnt;++i) {
            if(st[i]!=st[i-1]) st[t++]=st[i];
        }
        for(int i = 0; i < 1<<(n-k);++i){
            int s=0;
            for(int j=0;j<n-k;++j){
                if((i>>j)&1) s+=g[j+k];
            }
            int p = upper_bound(st,st+cnt, w-s) - st;
            if(p != cnt) ans = min(ans, abs(st[p]+s-w));
            if(p != 0) ans = min(ans, abs(st[p-1]+s-w));
        }
        return ans;
    }
};

将数组分成两个数组并最小化数组和的差

周赛 262.4

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成两个长度为 n 的数组，分别求出两个数组的和，并最小化两个数组和之差的绝对值。nums 中每个元素都需要放入两个数组之一。

请你返回最小的数组和之差。

数据范围

1 <= n <= 15
-1e7 <= nums[i] <= 1e7

class Solution {
public:
   
    int minimumDifference(vector<int>& g) {
        int n=g.size()/2, ans = INT_MAX;
        vector<vector<int>> f(n + 1), e(n + 1);
        for(int i=0;i<1<<n;++i){
            int s1=0, s2 = 0, x = 0;
            for(int j=0;j<n;++j){
                if(i>>j&1) s1 += g[j], s2 += g[j+n], x+=1;
                else s1 -= g[j], s2 -= g[j+n];
            }
            f[x].push_back(s1);
            e[x].push_back(s2);
        }
        for (int i = 0; i < n; ++i) {
            sort(f[i].begin(), f[i].end());
            sort(e[i].begin(), e[i].end());
        }
        for (int i = 0; i <= n; ++i) {
            for(int x: f[i]){ //前n个选i个，后n个选n-i个
                auto it= lower_bound(e[n - i].begin(), e[n - i].end(), -x);
                if (it != e[n - i].end()) {
                    ans = min(ans, abs(x + *it));
                }
                if (it != e[n - i].begin()) {
                    ans = min(ans, abs(x + *prev(it)));
                }
            }
        }
        return ans;
    }
};