计蒜客 买书 dfs

题目：

https://www.jisuanke.com/course/2291/182236

思路：

递归解决，从第一本书开始，每本书都有两种选择：

//index是book里面每本书价格的下标，

//money是目前的费用,cnt是计数现在买了几本书

1.买
dfs(index+1,money+book[index],cnt+1);

2.不买

dfs(index+1,money,cnt);//不买index这本书,往下一本书走

不断的递归进行选择，直到得出结果。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 using namespace std;

 //计蒜客 买书

 int m,n,k;

 int book[],vis[];//book存价格

 bool ok=false;//有没有解

 //index是book里面每本书价格的下标，

 //money是目前的费用,cnt是计数现在买了几本书

 void dfs(int index,int money,int cnt)

 {

     if(index>n)

     return;

     if(money>m||cnt>k)//剪枝

     return;

     if(money==m&&k==cnt)//满足条件

     {

         ok=true;

         return;

     }

     dfs(index+,money,cnt);//不买index这本书,往下一本书走

     dfs(index+,money+book[index],cnt+); 

 }

 int main()

 {

     while(scanf("%d%d%d",&m,&n,&k)==)

     {

         for(int i=;i<n;i++)

         {

             scanf("%d",&book[i]);

         }

         memset(vis,,sizeof(vis));

         ok=false;

         dfs(,,);

         if(ok)

         printf("Yes\n");

         else

         printf("No\n");

     }

     return ;

 }

计蒜客 买书 dfs的相关教程结束。