【题解】代金券组合

表示实现凑价格 最少需要几张优惠券，那么 就是要求的结果。
对于每张优惠券。都遍历一遍 。看一下加上这张优惠券能不能有更好的效果。

#include<iostream>

using namespace std;

const int INF = 0x3f3f3f3f;
int main()
{
    int P;
    int dp[10010]={0};
    while(cin >> P && P!=0)
    {
        int N;
        cin >> N;
        int v;
        for(int i = 0 ; i <= P ; i++)
        {
            dp[i]=INF;
        }
        for(int i = 0 ; i < N ; i++)
        {
            cin >>v;
            dp[v] = 1;//有价值为v的优惠券，那么v的价格就可以用一张优惠券拼成 这个一定是最优的方案
            for(int i = v+1 ; i <= P ; i++)
            {
                if(dp[i-v]!=INF)//如果i-v有方案那说明i的价格可以从i-v加一张价值为v的优惠券拼成
                {
                    dp[i]=min(dp[i],dp[i-v]+1); //看一下可不可以更优
                }
            }
        }
        if(dp[P]==INF)
        {
            cout<<"Impossible"<<endl;
        }
        else{
            cout<<dp[P]<<endl;
        }
    }
    return 0;
}