题目描述
给定N个正整数A1,A2,…,AN,从中选出若干个数,使它们的和为M,求有多少种选择方案。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数,表示A1,A2,…,AN。
输出格式
包含一个整数,表示M。
数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000
样例
输入样例:
4 4
1 1 2 2
输出样例:
3
算法
每样物体,只允许拿一次,这其实就是变形的01背包问题
数组dp[i]所存的内容就是,总和为i时的方案数
首先总和为0的情况只有一种,就是每一样物体我都不放进去,所以dp[1]为1;
而后每一次遍历时,需要判断dp[j-V[i]]是否为0,这句的意思其实是这样的:
当前需要看我把第i件物体放进去后,总和能不能达到 j ,而第i件物体只有V[i],
可能会不够,所以我们需要拿其他的来凑,即我们需要dp[j-V[i]],
当dp[j-V[i]]==0时,其实就表示能凑到总和为 j-V[i] 的方案数为0,是不是就表示不能凑到j-V[i]
而当dp[j-V[i]]!=0时,其实就表示能凑到总和为 j-V[i] 的方案数不为dp[j-V[i]],
是不是dp[j-V[i]]种方案可以和V[i],一起构成总和为 j, 所以dp[j]+=dp[j-V[i]
遍历一遍,最后dp[M]就是最后的方案数
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int N,M;
int V[110];
int dp[10100];
cin>>N>>M;
for(int i=1;i<=N;i++){
cin>>V[i];
}
memset(dp,0,sizeof dp);
sort(V+1,V+1+N);
dp[0]=1;
for(int i=1;i<=N;i++){ //每一样物体
for(int j=M;j>=V[i];j--){ //遍历总和的情况
if(dp[j-V[i]]!=0){
dp[j]+=dp[j-V[i]];
}
}
}
cout<<dp[M]<<endl;
return 0;
}