以前一想到學貪心的時候學到了，其實貪心算法的應用是前提的，在當前情況的幣值下，例如我們常見 1,2 ，5,10都是精心設計的。其實大多數應該用動態規劃，當然本文只用了搜素。具體思路看下面的連接。

http://www.acmerblog.com/dp6-coin-change-4973.html根據這個博客學習了下，我是按照我以前寫的整數分解來寫的，其實主要是分解的時候防止重復 例如 1 2 和 2 1是一樣的，在整數分解中用的是保證數組是遞增的，如 10分解 現實 1 1 2 後面的數都大於等於前面的數，

硬幣找零不就是整數分解

#include<stdio.h>
#include<iostream>
#include <vector>
using namespace std;
int count( int S[], int m, int n )
{
    // 如果n為0，就找到了一個方案
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    // 沒有硬幣可用了，也返回0
    if (m <=0 )
        return 0;
    // 按照上面的遞歸函數
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
int count1(int S[],int len,int left,int ans[],int lev)//ans lev配合使用，取得答案，可以使用vertor
{
    if(left<0) return 0;
    if(left==0)
    {
       

        return 1;
    }
    int sum=0;

    for(int k=0;k<len;k++)
    {
       
        if(ans[lev]<=S[k])
        {
            ans[lev+1]=S[k];
           
        int a=count1(S,len,left-S[k],ans,lev+1);

    //    cout<<a<<endl;
            sum+=a;
        }
    
        
   
   
    }

    return sum;
}

 

 

// 測試
int main()
{
    int i, j;
    int arr[] = {1, 2, 3,5,6,7,8,9};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 14));
    vector<int> v;
    int *ans=new int[20];
    ans[0]=-1;
    cout<<"my code:::"<<count1(arr,m,14,ans,0)<<endl;
    getchar();
    return 0;
}

#include<stdio.h>
#include<iostream>
#include <vector>
using namespace std;
int count( int S[], int m, int n )
{
    // 如果n為0，就找到了一個方案
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    // 沒有硬幣可用了，也返回0
    if (m <=0 )
        return 0;
    // 按照上面的遞歸函數
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
int count1(int S[],int len,int left,int ans[],int lev)//ans lev配合使用，取得答案，可以使用vertor
{
    if(left<0) return 0;
    if(left==0)
    {
        

        return 1;
    }
    int sum=0;

    for(int k=0;k<len;k++)
    {
        
        if(ans[lev]<=S[k])
        {
            ans[lev+1]=S[k];
            
        int a=count1(S,len,left-S[k],ans,lev+1);

    //    cout<<a<<endl;
            sum+=a;
        }
     
         
    
    
    }

    return sum;
}





// 測試
int main()
{
    int i, j;
    int arr[] = {1, 2, 3,5,6,7,8,9};
    int m = sizeof(arr)/sizeof(arr[0]);
    printf("%d ", count(arr, m, 14));
    vector<int> v;
    int *ans=new int[20];
    ans[0]=-1;
    cout<<"my code:::"<<count1(arr,m,14,ans,0)<<endl;
    getchar();
    return 0;
}