假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝，用这些硬币组合够成一个给定的数值n。例如n=200，那么一种可能的组合方式为 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100. 问总过有多少种可能的组合方式？ (这道题目来自著名编程网站ProjectEuler, 点击这里查看原题目) 类似的题目还有：

[华为面试题] 1分2分5分的硬币三种，组合成1角，共有多少种组合

[创新工厂笔试题] 有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱

    最近同事在项目中遇到了类似如此问题，需要在几个可重复数字中找出相加得到一个值的所有可行排列，一开始没有想出来，但记得大学的时候acm的题目中好像有类似的，与是便重温了一下这个经典题目。

    问题分析

给定一个数值sum，假设我们有m种不同类型的硬币{V1, V2, ..., Vm}，如果要组合成sum，那么我们有

sum = x1 * V1 + x2 * V2 + ... + xm * Vm 

求所有可能的组合数，就是求满足前面等值的系数{x1, x2, ..., xm}的所有可能个数。

　　[思路1] 当然我们可以采用暴力枚举，各个系数可能的取值无非是x1 = {0, 1, ..., sum / V1}, x2 = {0, 1, ..., sum/ V2}等等。这对于硬币种类数较小的题目还是可以应付的，比如华为和创新工厂的题目，但是复杂度也很高O（sum/V1 * sum/V2 * sum/V3 * ...）

　　[思路2] 从上面的分析中我们也可以这么考虑，我们希望用m种硬币构成sum，根据最后一个硬币Vm的系数的取值为无非有这么几种情况，xm分别取｛0, 1, 2, ..., sum/Vm｝，换句话说，上面分析中的等式和下面的几个等式的联合是等价的。

sum = x1 * V1 + x2 * V2 + ... + 0 * Vm

sum = x1 * V1 + x2 * V2 + ... + 1 * Vm

sum = x1 * V1 + x2 * V2 + ... + 2 * Vm

...

sum = x1 * V1 + x2 * V2 + ... + K * Vm  

　　其中K是该xm能取的最大数值K = sum / Vm。可是这又有什么用呢？不要急，我们先进行如下变量的定义：

dp[i][sum] = 用前i种硬币构成sum 的所有组合数。

　　那么题目的问题实际上就是求dp[m][sum]，即用前m种硬币（所有硬币）构成sum的所有组合数。在上面的联合等式中：当xn=0时，有多少种组合呢？ 实际上就是前i-1种硬币组合sum，有dp[i-1][sum]种！ xn = 1 时呢，有多少种组合？ 实际上是用前i-1种硬币组合成(sum - Vm)的组合数，有dp[i-1][sum -Vm]种; xn =2呢， dp[i-1][sum - 2 * Vm]种，等等。所有的这些情况加起来就是我们的dp[i][sum]。所以：dp[i][sum] = dp[i-1][sum - 0*Vm] + dp[i-1][sum - 1*Vm]

+ dp[i-1][sum - 2*Vm] + ... + dp[i-1][sum - K*Vm]; 其中K = sum / Vm

　　换一种更抽象的数学描述就是：

    通过此公式，我们可以看到问题被一步步缩小，那么初始情况是什么呢？如果sum=0，那么无论有前多少种来组合0，只有一种可能，就是各个系数都等于0；

dp[i][0] = 1   // i = 0, 1, 2, ... , m

　　 如果我们用二位数组表示dp[i][sum], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。如果前0种硬币要组成sum，我们规定为dp[0][sum] = 0. 

【参考】：参考地址

    程序源码

c++代码：

/* 
 * Filename :coins.cpp
 * Description: solve coin combinations using dynamic programing
 * Complier: g++
 * Author: python27
 */
#include <iostream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

/****************************************************************
 * coin Combinations: using dynamic programming
 *
 * Basic idea:
 * dp[i][j] = sum(dp[i-1][j-k*coins[i-1]]) for k = 1,2,..., j/coins[i-1]
 * dp[0][j] = 1 for j = 0, 1, 2, ..., sum
 * 
 * Input:
 * coins[] - array store all values of the coins
 * coinKinds - how many kinds of coins there are
 * sum - the number you want to construct using coins
 *
 * Output:
 * the number of combinations using coins construct sum
 *
 * Usage:
 * c[3] = {1, 2, 5};
 * int result = coinCombinations(c, 3, 10);
 *
 ****************************************************************/
int coinCombinations(int coins[], int coinKinds, int sum)
{
    // 2-D array using vector: is equal to: dp[coinKinds+1][sum+1] = {0};
    vector<vector<int> > dp(coinKinds + 1);
    for (int i = 0; i <= coinKinds; ++i)
    {
        dp[i].resize(sum + 1);
    }
    for (int i = 0; i <= coinKinds; ++i)
    {
        for (int j = 0; j <= sum; ++j)
        {
            dp[i][j] = 0;
        }
    }

    //init: dp[i][0] = 1; i = 0, 1, 2 ..., coinKinds
    //Notice: dp[0][0] must be 1, althongh it make no sense that
    //using 0 kinds of coins construct 0 has one way. but it the foundation
    //of iteration. without it everything based on it goes wrong
    for (int i = 0; i <= coinKinds; ++i)
    {
        dp[i][0] = 1;
    }

    // iteration: dp[i][j] = sum(dp[i-1][j - k*coins[i-1]])
    // k = 0, 1, 2, ... , j / coins[i-1]
    for (int i = 1; i <= coinKinds; ++i)
    {
        for (int j = 1; j <= sum; ++j)
        {
            dp[i][j] = 0;
            for (int k = 0; k <= j / coins[i-1]; ++k)
            {
                dp[i][j] += dp[i-1][j - k * coins[i-1]];
            }
        }
    }

    return dp[coinKinds][sum];
}

int main()
{
    int coins[8] = {1, 2, 5, 10, 20, 50, 100, 200};
    int sum = 200;
    int result = coinCombinations(coins, 8, 200);
    cout << "using 8 kinds of coins construct 200, combinations are: " << endl;
    cout << result << endl;
    return 0;
}

转换成PHP代码：

$coins = array(1,2,3);
$sum = 6;
$dp = array();

for($i = 0; $i < count($coins) + 1; $i++){
	for($j = 0; $j < $sum + 1; $j ++){
		$dp[$i][$j] = 0;
	}
}

for($i = 0; $i <= count($coins); $i++){
	$dp[$i][0] = 1;
}

for($i = 1; $i <= count($coins); $i++){
	for($j = 1; $j <= $sum; $j++){
	    $dp[$i][$j] = 0;
		for($k = 0; $k <= floor($j/$coins[$i-1]); $k++){
		    
            $dp[$i][$j] += $dp[$i-1][($j - $k*$coins[$i-1])];

		}
	}
}

echo $dp[count($coins)][$sum];

另外的一种思路，采用递归的方式：

c++代码：

#include <iostream>
#include <vector>
using namespace std;

void Combination(int *a, int n, int index, int sum, vector<int>& vec)
{
	if (sum == 0)
	{
		vector<int>::iterator iter = vec.begin();
		for (; iter != vec.end(); ++iter)
		{
			cout << *iter << " ";
		}
		cout << endl;
	}

	if (sum<0)
		return;

	for (int i = index; i<n; i++)
	{
		vec.push_back(a[i]);
		Combination(a, n, i, sum - a[i], vec);
		vec.pop_back();
	}

}


void PrintCombination(int *coins, int n, int sum)
{
	//int a[4] = { 1,2,5,10 };
	vector<int> vec;
	Combination(coins, n, 0, sum, vec);
}

void main()
{
	int sum;
	int n;
	cout << "输入金币种类:"<<endl;
	cin >> n;
	int *coins = new int[n];
	cout << "以此输入金币面额:"<<endl;
	for (int i = 0; i < n; i++) {
		cin >> coins[i];
	}
	cout << "输入总数值:"<<endl;
	cin >> sum;
	cout << sum << "分钱的组合情况如下：" << endl;
	PrintCombination(coins, n, sum);
}

转换成PHP代码：

function com($coins, $num, $index, $sum, $vector, Array &$all_com){
	if($sum == 0){
		/*foreach ($vector as $v){
			echo $v . ",";
		}
		echo "<br/>";*/
	    $all_com[] = $vector;
	}
	
	if($sum < 0 ) return ;
	
	for($i = $index; $i < $num; $i++){
		array_push($vector, $coins[$i]);
		com($coins, $num, $i, $sum - $coins[$i], $vector, $all_com);
		array_pop($vector);
	}
}


$vector = array();
$coins = array(1,2,3);
$sum = 6;
$num = count($coins);
$all_com = array();
com($coins, $num, 0, $sum, $vector, $all_com);
echo "<pre>";
print_r($all_com);
echo "</pre>";