关于dfs做法的解题思路

dfs + 剪枝

剪枝?

1.优化搜索顺序
2.排除等效冗余
3.可行性剪枝
4.最优性剪枝
5.记忆化

1. 首先我们知道, 每一节的木棍不超过五十, 而数据数不超过60, 所以, 使用桶排序可以很好的优化搜索, 而题目要求找出最小的木棒长度, 所以每次需要优先搜索木棒数量最多时对应的木棍长度,所以第一次搜索的结果就是最优解;

2. 只要拼接失败, 直接剪枝,因为每次搜索找到所有组合类型

c++ 代码及其详解

#include<iostream>
#include<cstring>
using namespace std;
const int N = 55;
int a[N];
//sum记录木棍的总长度, mx记录最大木棍长度, len记录目标每个木棒长度
int sum, mx, len;

bool dfs(int cnt, int now, int mxx, int len)
{
    if(cnt == 0) return true;//如果cnt == 0, 则目标木棒已拼接完成

    if(now == len)
    {
        //拼接成功, 开始拼接下一根
        if(dfs(cnt - 1, 0, mx, len)) return true;
    }

    for(int i = mxx; i > 0; i--)
    {
        if(a[i] && i + now <= len)
        {
            a[i]--;
            if(dfs(cnt, now + i, i, len)) return true;

            a[i]++;//还原
            if(now == 0 || now + i == len) return false;//第一次失败和第一次拼接完整后失败,直接剪枝
        }

    }
    return false;
}

int main()
{
    int n, t;
    cin >> n;
    while(n)
    {
        //初始化操作
        memset(a, 0, sizeof(a));
        sum = len = mx = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> t;
            a[t]++;
            sum += t;
            mx = max(mx, t);
        } 
        //目标木棒的长度从小到大枚举
        for(int i = mx; i <= sum; i++)
        {   
            //如果无法整除, 则跳过
            if(sum % i) continue; 
            //如果目标长度的二倍高于总和, 则目标为木棍长度总和
            if(i * 2 > sum)
            {
                cout << sum << endl;
                break;
            }
            //如果可整除且结果可以拼凑出合法的木棒,则输出;
            if(dfs(sum / i, 0, mx, i))
            {
                cout << i << endl;
                break;
            }
        }

        cin >> n;
    }

    return 0;
}