题解 | #最小邮票数#01背包解法

#include <bits/stdc++.h>
using namespace std;
int main() {
    int totalCent,n;
    cin>>totalCent>>n;
    int values[n+1];
    values[0]=0;
    for(int i=1;i<=n;i++)
        cin>>values[i];
    int dp[n+1][totalCent+1];//dp[i][j]表示前i个物品凑出重量为j的最小邮票数目
    //全部初始化为999(因为要找的是最少邮票数目)
    for(int i =0;i<=n;i++)
        for(int j=0;j<=totalCent;j++)
            dp[i][j] = 999;
    dp[0][0]=0;
    for(int i =1;i<=n;i++)
        for(int j=0;j<=totalCent;j++){
            if(j==0)
                dp[i][j] = 0;
            else{
                if(values[i]<=j){
                    //可以放得下
                    dp[i][j] = min(dp[i-1][j-values[i]]+1,dp[i-1][j]);
                }else{
                    //背包放不下这个物品
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        //输出目标面值中最小的元素（如果是999，返回0）999表示凑不出该面值的邮票
        int minNum = 999;
        for(int i =1;i<=n;i++){
            if(dp[i][totalCent]<minNum){
                minNum = dp[i][totalCent];
            }
        }
        cout<<(minNum==999?0:minNum)<<endl; 
}
// 64 位输出请用 printf("%lld")

01背包问题