【0-1背包】最小邮票数

/* 这类问题感觉叫0-1背包不知道标准不标准
 * 但明确dp之后，求解方式和0-1背包基本一致
 * dp[i][j]:表示前i张邮票凑成j面额所需要最少的邮票数
 * (1) 选第i张  ==> dp[i][j] = dp[i-1][j-w[i]] + 1（选i所以邮票数+1）
 * (2) 不选第i张==> dp[i][j] = dp[i-1][j]         （不选i所以邮票数不累积）
 * 状态转移方程：
 *     dp[i][j] = min(dp[i-1][j],dp[i-1][j-w[i]] + 1);
 * 除了min之外，和0-1背包就完全一样了，因此也可以空间优化为一维dp[v]
 * 如果简化为一维dp，有一个问题就是初始化
 * dp[0] = 0   其它dp[v]=INF
 * 其实这就是高赞回答里的*矩阵*，结合矩阵就会发现INF不影响后续计算
 */

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxV = 101;
const int maxN = 21;
const int INF = 1000000000;
int dp[maxV];        //如果是二维dp[i][j], 其实内容是一个下三角矩阵（省略了很多行的下三角矩阵，我当前的理解，不知道对不对）
int w[maxN];

int main(){
    int N,V;        //V即为题目中的M
    while(cin>>V>>N){
        for(int i=0;i<N;i++){
            cin>>w[i];
        }
        fill(dp,dp+maxV,INF);
        dp[0] = 0;
        for(int i=0;i<N;i++){
            for(int j=V;j>=w[i];j--){
                dp[j] = min(dp[j],dp[j-w[i]]+1);
            }
        }
        if(dp[V]!=INF)
            cout<<dp[V]<<endl;
        else
            cout<<"0"<<endl;
    }
    return 0;
}