题解 | 神奇的口袋

//背包问题的变种，这里是求方案数
#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<vector>
using namespace std;
int main()
{
	int n;//n是数量 
	cin>>n;
	vector<int> arr(n+1);//arr是体积。40是总容量，价值是1 
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
	}
	vector<int> dp(41,0);
	dp[0]=1;//当背包容量为0时只有1种方案 
	for(int i=1;i<=n;i++)
	{
		for(int j=40;j>=arr[i];j--)
		{
			dp[j]=dp[j]+dp[j-arr[i]];
		}
	}
	cout<<dp[40];
	return 0;
}