拿与不拿的dfs

在n个物品中拿k个，使得花费恰好为m。

典型的dfs，对每一个物品，可以选择拿与不拿，然后在判断下一个物品。

失败的dfs：

代码没有保存，只重写一下dfs函数的关键部分：

for(int i=0;i<n;i++)
{
    if(!vis[i])
    {
        vis[i]=1;
        if(dfs(sum+book[i],num+1)||dfs(sum,num)) return true;
        vis[i]=0;
    }
    return false;
}

对每一个选和不选，都有30层深度。30^30，即使剪枝，优化也不大。

成功的dfs：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int vis[35];
int book[35];
bool dfs(int sum,int num,int id)
{

    if(sum==m&&k==num) return true;
    if(num>k) return false;
    if(sum>m) return false;
    if(id>=n) return false;
    if(dfs(sum+book[id],num+1,id+1)||dfs(sum,num,id+1)) return true;
    return false;

}
int main()
{


    cin>>m>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>book[i];
    }
    memset(vis,0,sizeof(vis));
    if(dfs(0,0,0)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

上面这样dfs才是类似一个二叉树，复杂度2^30。。通过剪枝优化时间。