给定 N 个正整数 A1,A2,…,AN,从中选出若干个数,使它们的和为 M,求有多少种选择方案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数,表示 A1,A2,…,AN。
输出格式
包含一个整数,表示可选方案数。
数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。
输入样例:
4 4
1 1 2 2
输出样例:
3
状态分析:
代码实现:
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+5;
int dp[N];
int main(){
int n,m;
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=n;i++){
int x;
cin>>x;
for(int j=m;j>=x;j--)dp[j]=max(dp[j],dp[j]+dp[j-x]);
}
cout<<dp[m]<<endl;
return 0;
}
标签:组合,int,A1,A2,278,include,dp,AcWing From: https://www.cnblogs.com/hxss/p/17280148.html