多重部分和问题（多重背包+二进制优化）

时间限制: 1 Sec  内存限制: 64 MB 提交: 18  解决: 14

题目描述

有n种不同大小的数字，每种各个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。

输入

首先是一个正整数T(1<=T<=100) 接下来是T组数据 每组数据第一行是一个正整数n(1<=n<=100)，表示有n种不同大小的数字 第二行是n个不同大小的正整数ai(1<=ai<=100000) 第三行是n个正整数mi(1<=mi<=100000)，表示每种数字有mi个 第四行是一个正整数K(1<=K<=100000)

输出

对于每组数据，如果能从这些数字中选出若干使它们的和恰好为K，则输出“Yes”，否则输出“No”，每个输出单独占一行

样例输入

2 3 3 5  8 3 2 2 17 2 1 2 1 1 4

样例输出

Yes No 思路：有mi个啊ai，则可以把每个ai看成独立的数，比如例子上有3个3，2个5，2个8，我们可以看成7个独立的数，看看 把这7个数怎样组合可以得到k，这就变成了01背包问题。思想懂了就要优化了，想想依稀有100个数，没个数也有100， 一共就有10000个数，这样肯定会超时，所以用到了二进制优化，比如有20个3，就可以把3 分成1，2，4，8，5个3 等。 然后20以内的数都可以用这几个数表示。 100以内都可以用1，2，4，8，16，32，37个数来表示， #include <stdio.h> #include <string.h> #include <algorithm> int dp[100005]; int a[105],w[105]; int main() { using namespace std; int t; scanf("%d",&t); int n; int k; int i,j,l; int ans; while(t--) { scanf("%d",&n); for(i=1; i <= n; i++) { scanf("%d",&a[i]); } for(i=1; i <= n; i++) { scanf("%d",&w[i]); } scanf("%d",&k); memset(dp,0,sizeof(dp)); for(i=1; i<=n; i++) { if(dp[k]==k) { break; } if(a[i]*w[i] >= k)//如果它大于K，则在k范围内可以看成这个数是无穷的 { for(j=a[i]; j <=k; j++)//所以j可以从下到大累加 { dp[j] = max(dp[j-a[i]]+a[i] , dp[j]); } } else { ans=1; while(w[i] >= ans) { for( j=k; j >= ans*a[i]; j--) { dp[j] = max(dp[j-ans*a[i]]+ans*a[i] , dp[j]); } w[i] -= ans; ans <<= 1;//相当于ans *= 2;但是比它快。 } for( j=k; j >= w[i]*a[i]; j--) { dp[j] = max(dp[j-w[i]*a[i]]+w[i]*a[i] , dp[j]); } } } if(dp[k]==k) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }