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