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;
}