1068. Find More Coins (30)-白红宇

1068. Find More Coins (30)

阅读量：4070 次

发布时间：2019-05-25

本文共 798 字，大约阅读时间需要 2 分钟。

传送门:

AC 代码 .典型的BFS 并进行剪枝处理,有方案时剩下的不用执行因为此方案必定是最小的.

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          using namespace std;vector
           
            
             >allCase;void bfs(int targetMoney,vector
             
              coins,int start,vector
              
               curPath,bool &flag){ for (int i=start; i
               
                0){ curPath.push_back(coins[i]); bfs(diff, coins, i+1, curPath,flag); if(flag)//有方案 break; curPath.pop_back(); }else return; }}int main(){ int n,money,sum=0; scanf("%d %d",&n,&money); vector
                
                 coins(n); for (int i=0; i
                 
                  sum){ printf("No Solution\n"); return 0; } sort(coins.begin(),coins.end()); bool flag = false; bfs(money, coins, 0, vector
                  
                   (),flag); sort(allCase.begin(), allCase.end(), [](vector
                   
                    a,vector
                    
                     b){ if(a.size()!=b.size()) return a.size()>b.size(); else for (int i=0; i