勤工俭学 视频题解可点击此处查看 题目阅读 AC狗暑假在工地打工，手头有 K 种不同类型的钢管，他们长短不一，每种有 Xi 根，然后万恶的甲方要求AC狗用这些钢管焊接成程度为 L 的钢条。 题意抽象 给你一个长度 L , 问你利用手头的 K 种Xi条钢管，是否能拼接长度L 。 算法分析 此题可以选用 多重背包 书写 ，我们可以将最终能够拼接的长度 L 的最大值作为背包容纳的上限，每种钢管的长度视为价值与体积 w , 同时题目要求的最终目的是为了拼凑成长度L ，我们可以开一个数组布尔数组FLAG 记录下手头现有材料能够拼接的所有长度L，之后在进行询问的时候以长度作为下标直接输出Yes，No，即可。同时注意数据范围，如果按照多重背包的一个一个取的话会有 超时 的风险，所以我们还需要进行 二进制优化 。避免超时。 代码讲解