题目描述
Jimmy 到 Symbol 的手表店买手表，Jimmy 只带了 nn 种钱币，第 ii 种钱币的面额为 ki 元，张数为 ai 张。Symbol 的店里一共有 m 块手表，第 i 块手表的价格为 ti 元。
Symbol 的手表店不能找零，所以 Jimmy 只能在凑出恰好的钱数时才能购买一块手表。现在对于店里的每块手表，Jimmy 想知道他能不能凑出恰好的钱数进行购买。
输入格式
第一行两个空格分隔的整数 n 和 m 表示钱币数与手表数。
接下来 nn 行每行两个空格分隔的整数 ki 和 ai 表示钱币的面额和张数。
第 n+2 行，共 m 个用空格分隔的整数 ti，表示每块手表的价格。
输出格式
一共 m 行，对于第 i 行，如果能凑出恰好的钱数购买第 i 块手表则输出 Yes 否则输出 No，注意只有首字母大写。
输入样例
3 5
1 2
5 1
6 3
3 19 21 1 7
输出样例
No
Yes
No
Yes
Yes
样例解释
- 第二块手表 19=6×3+1=6×2+5+1×2，可以恰好凑出。
- 第四块手表 1=1×1，可以恰好凑出。
- 第五块手表 7=5+2×1=6×1+1，可以恰好凑出。
解法1：
思路分析：此题转化为子集和问题即可解决
C++代码如下：
#include <iostream>
using namespace std;
int x=0,q[100000010],n,m,nn=0;//n为钱币有多少种种类 ，nn为钱币总张数
void FixedSum(int* a, int num, int t, int sum)
{
if(sum == 0)
x=1;
else
{
if(t == num)
return ;
else
{
if(sum - a[t] >= 0)
FixedSum(a, nn, t + 1, sum - q[t]) ;
if(sum >= 0)
FixedSum(a, nn, t + 1, sum) ;
}
}
}
int main()
{
cin>>n>>m;
int k,a;
for(int i=0;i<n;i++)
{
cin>>k>>a;
for(int j=0;j<a;j++)//展开储存，如例中6，3转为6，6，6储存
{
q[nn]=k;
nn++;
}
}
for(int i=0;i<m;i++)
{
int sum;
cin>>sum;
FixedSum(q, nn, 0, sum);
if(x)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
x=0;
}
return 0;
}
解法2：
思路分析：
这个题目就是变形的多重背包，那么不难想到，用一个 5×10^5 的 bool 数组来 dp 每个数能否被选中。
但是这样极限数据是 200×1000×5×10^5，直接爆炸，只能拿 50 pts。
接下来就是套路性的优化多重背包了：二进制优化。
比如有 a 个价值为 b 的物品，那么他们能组合出的就是 1×b,2×b,…a×b 价值的物品。
那么能不能构造另一些物品，让这些物品同样能组合出 1×b,2×b,…a×b 价值的物品呢？
可以的。
我们需要构造的是价值为 1×b,2×b,4×b,…2^n×b，其中这些物品价值的总和不超过a×b 且 n 尽量大。当然最后离 a×b 可能还有一些距离，所以要用一个价值为 (a−∑i=1n2n)×b 来弥补。
用二进制的位值原理法可以得出这个是正确的。首先，除最后的一个物品可以组合出 价值 1×b∼(2n+1−1)×b 价值的物品。然后再搭配最后一个物品就可以组合出全部物品了。
好处是物品数量由 a 下降到了 loga，但是 200×10×5×105 似乎还是过不了
那么还有一个好东西：bitset
上面的 dp 看起来是这个样子的：
for(j=5e5-l*k;j>=0;j--)
if(dp[j])
dp[j+l*k]=1;
那不就是位运算吗？说清楚一些，如果把 dp 数组当作一个大 bool 类型，那么这个操作就等同于 dp|=dp<<l*k。
正好，万能的 STL 库中就有这个好东西 bitset，本质上是一个 bool 数组（内置是用 ull 压了位），但是仍然支持各种位运算。
这样定义：
bitset<500005> dp;
操作也很简洁：
dp|=dp<<l*k;
AC的C++代码如下：
#include<bits/stdc++.h>
using namespace std;
bitset<500005> dp;
int main()
{
int n,m,i,j,a,k,t;
cin>>n>>m;
dp[0]=1;
for(i=0;i<n;i++)
{
cin>>k>>a;
for(j=1;a>=j;j*=2)
{
dp|=dp<<j*k;
a-=j;
}
if(a*k)
dp|=dp<<a*k;
}
while(m--)
{
cin>>t;
if(dp[t])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
