这个问题是一个典型的背包问题，可以使用动态规划来解决。定义一个二维数组 dpdpdp ，其中 dpdpdp [ iii ][ jjj ] 表示前 iii 个物品放入容量为 jjj 的背包的方案数。则动态规划的状态转移方程为： dpdpdp [ iii ][ jjj ] === dpdpdp [ i−1i-1i−1 ][ jjj ] +++ dpdpdp [ i−1i-1i−1 ][ j−wj-wj−w [ iii ]]

看起来跟背包有紧密的联系，实际没有。 这就是一个dp题。

#include<bits/stdc++.h> using namespace std; int a[1000]; int dp[1000]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } dp[0]=1; for(int i=1;i<=n;i++) { for(int j=m;j>=a[i];j--) { if(j>=a[i]) { dp[j]=dp[j]+dp[j-a[i]]; } } } cout<<dp[m]; return 0; }