题目大意：

有各种不同面值的货币，每种面值的货币有不同的数量，请找出利用这些货币可以凑成的最接近且小于等于给定的数字cash的金额。

初始思路：

多重背包问题，第i种面额d[i]有 n[i]+1种选择方案

可以转化为01背包问题处理

转化的大概思路就是把 每种面值乘以其不同的个数，把得到的不同金额作为一件新的独一无二的货币，但是这样存在两个问题，一是 d[i]*ki 可能等于 d[j]*kj ，其中ki ∈n[i]，kj∈n[j]，二是这样做一定TLE超时

解题思路：

首先解决存储问题，cash上限实在太大了..10W，推荐用new，最后记得delete就是了，不然就算AC掉，Memory也会很大

言归正传，下面的解题思路最好配合我写的程序去看，不然很难看懂，而且看之前请保证你对01背包、完全背包、多重背包的理论知识有所了解。。。不然应该看不懂的。。。

本题输入有4个部分：

cash //背包容量（最大可取金额）

N //物品种数（面额种数）

n[i]第i种物品的个数（第i种面额的数量）

d[i]第i种物品的价值（第i种面额的价值）

值得注意的是，如果设每个物品的价值为w[i]，体积（可理解为消耗的价值）为c[i],那么必有 d[i] = w[i] = c[i]

如果把一个金额看为一种状态，那么一共有0~cash种状态

显然其中可能会发生的状态范围为min{w[i] | 1<=i<=n[i]} ~ Cash

那么可以建立一个状态数组dp[cash+1]，

其中dp[j]记录的是“最接近状态j，且<=j”的状态值，即dp[j] <=j

J越接近dp[j]，dp[j]的解越优，最理想是dp[j]=j

需要注意的是，dp[j]为了说明的是状态j可以发生，但不会理会dp[j]怎样发生

例如有3张1元，1张3元

那么我们既可以认为dp[3]=3是通过取3次1元得到，也可以认为dp[3]是通过取1次3元得到的，但无论怎样得到，dp[3]=3都会发生,

再需要注意的是，dp[j]的状态值会累积

再形象举例说明：例如有1张3元,cash=4

那么根据前面的说明，自然有dp[3]=dp[4]=3，就是说状态3、状态4都可以通过取1次3元发生，一旦发生，这个状态值3就会被保有在当前的状态dp[4]，这其实是起到一个优化作用，后面详细解释

再接上例，当我们增加一个条件“有3张1元”，那么在已经被保存的前提“dp[4]=3”下，我们只需要通过取1次1元，就能得到比dp[4]=3的更优解dp[4]=4，但此时我们完全不用理会dp[4]=3是怎样来的，我们只需要知道dp[4]=3一定会出现就足够了

然后说说刚才提到的“优化问题”

利用01背包的知识，不难理解 状态方程 dp[j]=dp[ j-c[i] ]+w[i]

至于说方程是什么含义，看过01背包的大概也知道什么意思，没看的同学就别怪我不解释咯O(∩_∩)O

优化是因为状态值被记录了，就是说我们在取得下一个货币i之前，当前的状态为j-c[i]

一旦我们选取货币i，就会得到状态（j-c[i]）+c[i]，即状态j 。且状态j的状态值dp[j]会加上w[i]。 至于dp[j]原来值是多少，就无需理会，因为dp[j]的值是累积下来的，同样本次加上w[i]后，只要dp[j]值未到最优，它同样会成为下一次的累加值。

这样每次都直接调用前一次已获得的状态值，就可以节省一堆搜索的时间，这是DFS或BFS办不到的，也是动态规划的优点。

接下来说说计数器count[j]

在我的程序中，每更换一次面额，计数器会清零，这样做是为了 以面额i的价值w[i]为权，根据选取该面额的个数，对状态值dp[j]进行w[i]的整数倍分割，这样就能得到对于每组状态dp[w[i]k]到dp[w[i]（k+1）] (0<=k<=n[i])之间，在当前面额w[i]下的最优状态值。

例如有 3张3元

自然dp[0]=dp[1]=dp[2]=0，count[0]= count[1]= count[2]=0这是因为最小面额为3

不难得到dp[3]=dp[4]=dp[5]=3，count[3]= count[4]= count[5]=1这是因为面额3元不可分，这3个状态的最优值就是取1次3元

dp[6]=dp[7]=dp[8]=6 , count[6]= count[7]= count[8]=2这3个状态的最优值就是取2次3元

dp[9]=dp[10]=dp[11]=dp[…]=9 ,count[9]= count[10]= count[[11]= count[…]=3 最多只有3张3元，以后的的状态的最优值均为9

//1052K  47MS 
 
#include <iostream>
#include <cstring>

int main(void) {
    int N;   // 物品种数（面额种数）
    int cash;  // 背包容量（最大可取金额）
    while (std::cin >> cash >> N) {
        /*Input*/
        int* n = new int[N + 1];  // n[i]第i种物品的个数（第i种面额的数量）
        int* w = new int[N + 1];  // w[i]第i种物品的价值（第i种面额的价值）
        int* c = new int[N + 1];  // c[i]第i种物品的体积（第i种面额消耗的价值）
        int* dp = new int[cash + 1];  // dp[j]记录的是 当前最接近状态j且<=j的值，dp值会累积
        int* count = new int[cash + 1];// 计数器，限制某种物品（面额）的选取个数

        for (int i = 1; i <= N; i++) {
            std::cin >> n[i] >> w[i];
            c[i] = w[i];    // 本题的单个物品的“体积”等于其“价值”
        }

        /*Initial*/
        memset(dp, 0, 4 * (cash + 1));  // 由于dp申请的是动态内存，用sizeof计算长度会出错
                                          // 这里要用 类型大小*个数,这里为 int*(cash+1), int大小为4

        /*DP*/
        for (int i = 1; i <= N; i++) {
            memset(count, 0, 4 * (cash + 1));  // 每更换一次面额，计数器清零
            for (int j = w[i]; j <= cash; j++)      // 对于第i种货币，其面额d[i]~cash间任一个状态都可能发生
                if (dp[j] < dp[j - c[i]] + w[i] && count[j - c[i]] < n[i]) // count[j-c[i]]<n[i]
                {                                               // 取某种面额前，必须保证这次操作之前所取该种面额的次数小于n[i]
                    dp[j] = dp[j - c[i]] + w[i];    // 选取第i个物品后，背包容量（允许取的最大金额）减少c[i]
                    count[j] = count[j - c[i]] + 1;   // 对于当前状态j，第i种面额被抽了count[j]次
                }
        }

        /*Output*/
        std::cout << dp[cash] << std::endl;

        /*Release Space*/
        delete[] n;
        delete[] w;
        delete[] c;
        delete[] dp;
        delete[] count;
    }

    return 0;
}