美团刷题 代金券组合

近期某商场由于周年庆，开启了“0元购”活动。活动中，消费者可以通过组合手中的代金券，实现0元购买指定商品。

聪明的小团想要用算法来帮助他快速计算：对于指定价格的商品，使用代金券凑出其价格即可，但所使用的代金券总面额不可超过商品价格。由于代金券数量有限，使用较少的代金券张数则可以实现价值最大化，即最佳优惠。

假设现有100元的商品，而代金券有50元、30元、20元、5元四种，则最佳优惠是两张50元面额的代金券；而如果现有65元的商品，则最佳优惠是两张30元代金券以及一张5元代金券。

请你帮助小团使用一段代码来实现代金券计算。

输入描述：

多组输入输出，读到s=0时结束 输入可以有多个测试样例，每个测试由两行组成。

其中第一行包含一个整数P，表示商品的价格，1≤P≤10000；输入P为0时表示结束。

第二行包含若干整数，使用空格分割。其中第一个整数N（1≤N≤20）表示有多少种代金券，其后跟随M个整数，表示手中持有的代金券面额（1≤N≤1000），每种代金券数量不限。

输出描述：

找到最少张数的代金券，使其面额恰好等于商品价格。输出所使用的代金券数量；

如果有多个最优解，只输出其中一种即可；

如果无解，则需输出“Impossible”。

示例输入

65
4 50 30 20 5
0

示例输出

3

思路：动态递归思想，设置一个数组来存放每个金额实现的数量，如果没有的话，则用无穷或者一种可以识别但又不甘于正常运行数字来代替，利用目标金额减去已有金额得到新的目标金额，将其最优（小）值加一（加上该已有金额组成目标金额）即为新的目标金额实现数量。

JS实现：

// while(true){
//     var num = parseInt(readline())
//     if(num==0){
//         break
//     }
//     var lines =readline()
//     var lineArr = lines.split(" ").map(Number)
//     var type = lineArr[0]
//     var money = lineArr.slice(1)
//     console.log(getResult(num,type,money))
// }
//以上代码为方面提交进行的输入处理
var num = 65;
var type = 4;
var money = [50,30,20,5];
function getResult(num, type, money) {
    var dp = [];
    dp[0] = 0;
    for(var i=1;i<=num;i++){
        var arr = [];
        for(var j=0;j<money.length;j++){
            if(i>=money[j]){
                arr.push(dp[i-money[j]] + 1);
            }
        }
        dp[i] = Math.min(...arr);
    }
    return dp[num] === Infinity?"Impossible":dp[num];
}
console.log(getResult(num,type,money))

C++实现：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define INF 0x3f3f3f

int main()
{
    int n, m;
    int money[10002];
    int dp[10002];
    while(scanf("%d", &n) && n)
    {
        for(int i=0;i<10002;i++)
        {
            dp[i] = INF;
        }
        dp[0] = 0;
        scanf("%d", &m);
        for(int i=0;i<m;i++)
        {
            scanf("%d", &money[i]);
        }
        for(int i=1;i<=n;i++)
        {
            int arr[10002];
            int k =0;
            for(int j=0;j<m;j++)
            {
                if(i>=money[j])
                {
                    arr[k++] = dp[i-money[j]] + 1;
                }
            }
            int minn = INF;
             for(int o=0;o<k;o++)
             {
                 if(arr[o] < minn)
                 {
                     minn = arr[o];
                 }
             }
             dp[i] = minn;
        }
        if(dp[n] == INF)
        {
            printf("Impossible\n");
        }
        else
        {
            printf("%d\n", dp[n]);
        }
    }
    return 0;
}