【Money Changing Problem】
Money Changing Problem 是一种常见的问题。Money Changing Problem 包括以下几种：
1、能否凑得某个价位（Money Changing Problem）；
2、凑得某个价位的凑法总数（Coin Changing Problem）；
3、凑得某个价位的最少（多）钱币用量（Change-Making Problem）；
4、凑得某个价位的最少（多）钱币种类；
5、所有无法凑得的价位种，最大的价位（Frobenius Number）；
6、所有无法凑得的价位总共有几种；
7、限制钱币用量，球的 Frobenius Number 加一（Postage Stamp Proble）。

下面我们开始逐一学习这些不同的 Money Changing Problem。
Money Changing Problem 其实就是 Unbounded Knapsack Problem（完全背包）变形：
物品变成钱币，物品重量变成面额，物品价值变成【凑得到，凑不到】两种情况，累计价值的方式从加法运行变成 OR 运算。
唯一要小心的是：表格的初始值，把 $0$ 元设定为可以凑到；但是正常情况下，是无法凑到 $0$ 元的。

这样我们可以退出以下的递推公式：
$\text{c(n,m)=c(n-1, m)           or (c(n, m-price[n])})$
                      ^^^^^                ^^^^^^^^^^^
                     不用这种钱币          用去一个钱币
其中：
$n$：用第 $0$ 种到第 $n$ 种钱币来凑的价位。
$m$：预凑得的价位值。
$\text{c(n, m)}$：用第 $0$ 种到第 $n$ 种钱币凑得价位 $m$ 的凑法数目。
$\text{price[n]}$：第 $n$ 种钱币的面额大小。
再具体代码实现上，我们有 top-down 和 bottom-up 两种方法。

【top-down】
int price[5]={5,2,6,11,17};//钱币面额，顺序可以任意


//-1表示没有计算过，一开始必须将数组初始化为 -1
//大于等于 0 表示该问题有计算过
int c[5][1000+10];


bool change(int n, int m) {
    if (n<0 || m<0) return 0;
    if (m==0) return 1;
    if (c[n][m]!=-1) return c[n][m];
    return c[n][m]=change(n-1, m) | change(n, m-price[n]);
}


【bottom-up】
int price[5]={5,2,6,11,17};//钱币面额，顺序可以任意
bool c[1000+10];


//看使用钱币能否凑到价位 m
void change(int m) {
    memset(c, false, sizeof(c));
    c[0]=true;


    //依次加入各种面额
    for (int i=0; i<5; i++) {
        //由低价位逐步到高价位
        for (int j=price[i]; j<=m; j++) {
            c[j] ||= c[j-price[i]];
        }
    }


    if (c[m]) {
       cout<<"凑得到\n";
    } else {
        cout<<"凑不到\n";
    }
}



【问题描述】
给定许多不同面额的钱币，能否凑得某个价位？每种面额的钱币都无限供应。

1

1