计蒜客买书

分析

dfs经典好题，对于每本书我们都有选或者不选两种抉择。

代码

#include<bits/stdc++.h>
using namespace std;
int m,n,k;//有m元，n本书，刚好k本；
int price[35];
int flag=0;
void dfs(int nowbook,int coin,int lastbook)
{
    if(flag==1) return;//符合条件，不再继续搜索
    if(lastbook==0&&coin==0)
    {
        flag=1;
    }//先判断符合条件的情况，若先判断不合法会提前返回
    if(coin==0||lastbook==0) return;//剪枝
    if(nowbook>n) return;
    dfs(nowbook+1,coin-price[nowbook],lastbook-1);
    dfs(nowbook+1,coin,lastbook);
}
int main()
{
    cin>>m
    >>n
    >>k;
    for(int i=1;i<=n;i++)
    {
        cin>>price[i];
    }
    dfs(1,m,k);
    if(flag==1) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}