勤工俭学

视频题解可点击此处查看

题目阅读

​ AC狗暑假在工地打工，手头有 K 种不同类型的钢管，他们长短不一，每种有 Xi 根，然后万恶的甲方要求AC狗用这些钢管焊接成程度为 L 的钢条。

题意抽象

​ 给你一个长度 L , 问你利用手头的 K 种Xi条钢管，是否能拼接长度L 。

算法分析

​ 此题可以选用 多重背包 书写 ，我们可以将最终能够拼接的长度 L 的最大值作为背包容纳的上限，每种钢管的长度视为价值与体积 w , 同时题目要求的最终目的是为了拼凑成长度L ，我们可以开一个数组布尔数组FLAG 记录下手头现有材料能够拼接的所有长度L，之后在进行询问的时候以长度作为下标直接输出Yes，No，即可。同时注意数据范围，如果按照多重背包的一个一个取的话会有 超时 的风险，所以我们还需要进行 二进制优化 。避免超时。

代码讲解

#include<bits/stdc++.h>
using namespace std;
int n,q;
int x,y;
bool f[500001];
int o,b[15],p;
int main(){
 cin>>n;
 f[0]=1;
 for(int i=1;i<=n;++i){
  scanf("%d%d",&x,&y);
  o=1;
  p=1;
  while(o<=y){
   y-=o;
   b[p]=o*x;
   o*=2;
   ++p;
  }
  o/=2;
  b[p]=y*x;
  for(int i=1;i<=p;++i)
  for(int j=500000;j>=b[i];--j)
  f[j]=f[j]||f[j-b[i]];
 }
 cin>>q;
 while(q--){
  scanf("%d",&x);
  if(f[x]) printf("Yes\n");
  else printf("No\n");
 }
 return 0;
}