回溯&分支限界(剪枝)

回溯

子集型（选或不选）

6.买瓜 - 蓝桥云课 (lanqiao.cn)

DFS+剪枝 主要有几种情况 不需要继续进行搜索

当sum > m的时候 必定不相等 当cnt > mcnt的时候 不会是最小

比较难想的是 对所有的瓜进行排序 当买到第i个的时候 如果后面所有瓜加起来都不能到m 那也是必定不相等的 这个就相当于往后多看了一步 就不用去走了

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<double>nums(100), suf(100);
int n, m;
int mcnt = 2e9;
void  dfs(int i, double sum, int cnt)
{
    if (cnt >= m)return ;
    if (sum == m)
    {
        mcnt = min(cnt, mcnt);
        return ;
    }
    if (i == n || sum > m || suf[i] + sum < m)
    {
      //  cout<<sum<<endl;
        return ;
    }
    dfs(i + 1, sum + nums[i], cnt);
    dfs(i + 1, sum, cnt);
    dfs(i + 1, sum + nums[i] / 2, cnt + 1);
    
}

int main()
{
    // 请在此输入您的代码
    
    cin>>n>>m;
    for (int i = 0; i < n; i++)cin>>nums[i];
    sort(nums.begin(), nums.end(), greater<>());
    for (int i = n - 1; i >= 0; i--)suf[i] = suf[i + 1] + nums[i];
    dfs(0, 0, 0);
    mcnt == 2e9 ? cout<< -1 : cout<<mcnt;
    return 0;
}

排列型（选哪个）