算法提高课汇总

算法思路

本题数据规模较小, 考虑用$dfs$求解.

搜索顺序

首先考虑$dfs$核心问题 — 搜索思路.

一种可行的搜索顺序: 依次对每只小猫枚举其能放入哪辆缆车🚡. 每只小猫🐱可选择当前存在
的所有缆车, 或者选择一辆新缆车.

可以简单证明上搜索顺序可以遍历所有方案:

• 按小猫🐱下标递增顺序搜索. 对于任意方案, 每辆缆车中小猫下标最小的对应选择: 新加入缆车;
  其余小猫对应加入已存在缆车.

  例如最终解为$(1, 3, 5), (0, 4), (2)$. 则0号小猫新加入缆车, 4号加入0号对应缆车.
  1号小猫新加入一辆缆车, 3、5加入1号小猫的缆车. 2号小猫新加入一辆缆车.

剪枝优化

参考$DFS$ 剪枝 , 本题可使用如下优化:

• 优化搜索顺序. 可以按小猫重量降序的顺序搜索, 也就是先考虑重的小猫. 小猫重量越重, 其缆车
  剩余承重越少, 后续可加入小猫越少 — 分支越少.

• 可行性剪枝: 判断🐱加入缆车后是否超重, 对于不可行 — 超重的分支, 可以直接返回.

• 最优性剪枝: 若当前分支缆车数不小于当前最优解, 可直接返回.

具体代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N], sum[N];
int ans = N;

void dfs(int u, int k)
{
    if ( k >= ans ) return; //最优性剪枝
    if ( u == n )
    {
        ans = k;
        return;
    }

    for ( int i = 0; i < k; i ++ ) //加入已有缆车
        if ( sum[i] + w[u] <= m )
        {//可行性剪枝
            sum[i] += w[u];

            dfs(u + 1, k);

            sum[i] -= w[u]; //恢复现场
        }

    sum[k] = w[u];
    dfs(u + 1, k + 1); //新加入一辆缆车
    sum[k] = 0; //恢复现场
}

int main()
{
    cin >> n >> m;
    for ( int i = 0; i < n; i ++ )  cin >> w[i];

    //优化搜索顺序
    sort(w, w + n);
    reverse(w, w + n);

    dfs(0, 0);
    cout << ans << endl;

    return 0;
}