1.数字组合

题目链接：数字组合 - 洛谷

标签：背包问题

注意点：将dp[0]初始化为1

AC代码：

#include<iostream>
using namespace std;

int dp[100005];

int main()
{
    int n,m,t;
    cin>>n>>m;
    dp[0]=1;
    for(int i=1;i<=n;++i)
    {
        cin>>t;
        for(int j=m;j>0;j--)
        {
            if(j>=t) dp[j]+=dp[j-t];
        }
    }

    cout<<dp[m]<<endl;

    return 0;
}

2.何以包邮

题目链接：4700. 何以包邮？ - AcWing题库

AC代码：

#include<iostream>
using namespace std;

const int MAXN = 300005;

int main()
{
    int n,m;
    int t;
    bool f[MAXN];
    cin>>n>>m;
    
    f[0]=true;
    for(int i=0;i<n;++i)
    {
        cin>>t;
        for(int j=MAXN;j>=t;j--)
        {
            if(f[j-t]) f[j]=true;
        }
    }
    
    for(int i=m;i<MAXN;i++)
    {
        if(f[i])
        {
            cout<<i<<endl;
            break;
        }
    }
    
    return 0;
}