🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 小米秋招笔试，来啦！！！

🍥 本次是DP+贪心场，第二题很容易误导往DP方面想，当然也能做只不过需要优化

1️⃣ 01背包的变种，即求01背包是否能恰好装满

2️⃣ 贪心，分别枚举递增和递减的情况，有任意一种满足即可

🧸 01.K小姐的玩具 评测链接🔗

问题描述

在一个阳光明媚的下午，K小姐决定整理她的玩具。她有一个容量为 的箱子，以及 个不同大小的玩具，每个玩具的大小分别为 。除了这些玩具，K小姐还有 个大小均为 的填充物，这些填充物是她参加各种活动时的纪念品。

K小姐希望能够将这些玩具和填充物放入箱子中，恰好装满箱子，不留任何空隙。她想知道是否可以通过选择一些玩具（包括填充物）来实现这个目标。

当然，如果填充物足够多，她也可以选择用填充物完全填满整个箱子，这样也会让她感到很开心！

输入格式

第一行包含一个整数 ，表示数据组数。

对于每组数据:

第一行包含三个整数 、 和 ，分别表示箱子的容量、玩具的数量以及填充物的数量。

第二行包含 个整数 ，分别表示这 个玩具的大小。

输出格式

输出 行，分别表示每组数据的答案。

对于每组数据，如果可以恰好装满箱子，输出 "YES"；否则输出 "NO"。

样例输入

2
10 4 1
2 3 5 7
10 1 3
6

样例输出

YES
NO

数据范围

• 每组数据中，箱子的容量、玩具数量和填充物数量均在上述范围内。

题解

动态规划

这个问题实际上是一个经典的背包问题。我们需要确定是否可以选择一些玩具和填充物，使得它们的总大小恰好等于箱子的容量 ：

动态规划：定义一个数组 dp，其中 dp[j] 表示是否可以用选定的玩具组合成大小为 的总和。初始时，dp[0] 为 true（表示不选任何玩具时总和为0）。

状态转移：对于每个玩具，从后向前更新 dp 数组，对于当前的玩具 a[i]，如果之前可以组合出大小为 j - a[i] 的总和，那么就可以组合出大小为 j 的总和。

检查结果：在更新完所有玩具后，我们检查从大到小的 dp 数组，如果存在某个 i 满足 dp[i] 为 true 且 N - i <= c（即剩余空间可以用填充物填满），则返回 "YES"；否则返回 "NO"。

参考代码

• Python

def can_fill_box(N, n, c, toys):
    # 如果填充物数量足够，可以直接返回 True
    if c >= N:
        return True
    
    # 初始化动态规划数组
    dp = [False] * (N + 1)
    dp[0] = True # 不选任何东西时，总和为0
    
    # 动态规划更新 dp 数组
    for toy in toys:
        for j in range(N, toy - 1, -1):
            dp[j] = dp[j] or dp[j - toy]
    
    # 检查是否能用剩余空间填满
    for i in range(N + 1):
        if N - i <= c and dp[i]: # 如果剩余空间可以被填满
            return True
            
    return False

# 主程序入口
if __name__ == "__main__":
    T = int(input()) # 输入数据组数
    results = []
    
    for _ in range(T):
        N, n, c = map(int, input().split()) # 输入箱子容量、玩具数量和填充物数量
        toys = list(map(int, input().split())) # 输入每个玩具的大小
        
        result = "YES" if can_fill_box(N, n, c, toys) else "NO"
        results.append(result)
    
    print("\n".join(results)) # 输出结果

• Java

import java.util.Scanner;

public class ToyBox {

    public static boolean canFillBox(int N, int n, int c, int[] toys) {
        if (c >= N) return true; // 如果填充物数量足够，可以直接返回 true
        
        boolean[] dp = new boolean[N + 1];
        dp[0] = true; // 不选任何东西时，总和为0
        
        // 动态规划更新 dp 数组
        for (int toy : toys) {
            for (int j = N; j >= toy; j--) {
                dp[j] |= dp[j - toy];
            }
        }
        
        // 检查是否能用剩余空间填满
        for (int i = N; i >= 0; i--) {
            if (N - i <= c && dp[i]) return true;
        }
        
        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int T = scanner.nextInt(); // 输入数据组数
        
        while (T-- > 0) {
            int N = scanner.nextInt();
            int n = scanner.nextInt();
            int c = scanner.nextInt();
            
            int[] toys = new int[n];
            for (int i = 0; i < n; i++) {
                toys[i] = scanner.nextInt(); // 输入每个玩具的大小
            }
            
            String result = canFillBox(N, n, c, toys) ? "YES" : "NO";
            System.out.println(result); // 输出结果
        }
        
        scanner.close();
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 函数用于判断是否可以将箱子装满
bool canFillBox(int N, int n, int c, vector<int>& toys) {
    if (c >= N) return true; // 如果填充物数量足够，可以直接返回 true
    
    vector<bool> dp(N + 1, false);
    dp[0] = true; // 不选任何东西时，总和为0
    
    // 动态规划更新 dp 数组
    for (int toy : toys) {
        for (int j = N; j >= toy; j--) {
            dp[j] |= dp[j - toy];
        }
    }
    
    // 检查是否能用剩余空间填满
    for (int i = N; i >= 0; i--) {
        if (N - i <= c && dp[i]) return true;
    }
    
    return false;
}

// 主程序入口
int main() {
    ios::sync_with_stdio(false);
    
    int T;
    cin >> T; // 输入数据组数
    
    while (T--) {
        int N, n, c;
        cin >> N