165. 小猫爬山

题目描述

每辆缆车承重一样，每个猫重量不一，最少需要多少缆车把猫运下山？

基本分析

1. 怎么考虑搜索？对当前的猫来说，有当前开的缆车个数+新缆车几种选择
2. 状态空间有哪些维度？当前用到的缆车个数，当前正在处理的猫的id
3. 哪些可额能的减枝方式？（1）优化搜索顺序：从大到小；（2）最优性：>=ans的结果不考虑了，直接return

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

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

// 当前开了多少缆车？处理到索引多少的猫？
void dfs(int cnt, int idx)
{
    if (cnt >= ans)
        return;
        
    if (idx == n)
    {
        ans = min(ans, cnt);
        return;
    }
    
    // 枚举可以放在哪个缆车上
    for (int i = 0; i < cnt; i++)
    {
        if (sum[i] + cat[idx] <= w)
        {
            //维护-向下-还原
            sum[i] += cat[idx];
            dfs(cnt, idx + 1);
            sum[i] -= cat[idx];
        }
    }
    //还可以开新的
    sum[cnt] = cat[idx];
    dfs(cnt + 1, idx + 1);
    sum[cnt] = 0;
}

int main()
{
    scanf("%d%d", &n, &w);
    
    for (int i = 0; i < n; i++)
        scanf("%d", &cat[i]);
    
    dfs(0, 0);
    
    printf("%d\n", ans);
    
    return 0;
}

总结

1. 明确状态空间需要定义的维度
2. 注意作用域