POJ 1285 - Combinations, Once Again 泛化背包

POJ 1285 - Combinations, Once Again 泛化背包

将选择的数目看成背包的空间...枚举放入某类数的个数..空间增加为当前枚举的个数..dp[j+x]+=dp[j]...(j为枚举的当前背包容量..j为枚举的当前某个类的个数)

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 55using namespace std; int n,num,a[MAXN],h[MAXN];ll dp[MAXN];int main(){ int T,i,j,x,m; T=0; while (~scanf("%d%d",&n,&m) && n && m) { for (i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); a[0]=num=0; for (i=1;i<=n;i++) if (a[i]!=a[i-1]) h[++num]=1; else h[num]++; memset(dp,0,sizeof(dp)); dp[0]=1; for (i=1;i<=num;i++) for (j=n;j>=0;j--) for (x=1;x<=h[i];x++) if (j+x<=n) dp[j+x]+=dp[j]; printf("Case %d:\n",++T); while (m--) { scanf("%d",&x); printf("%I64d\n",dp[x]); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。