笔试时间：2024年09月19日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

小明正在整理他的玩具，他遇到了一道有趣的装箱问题:他有一个容量为N的箱子，并且有n个大小为ai的玩具。除了这n个玩具外，还有c个大小均为1的填充物，它们是小明参加各种活动的纪念品，正好可以拿来填充缝隙。他的任务是确定是否可以选其中一些玩具(填充物也包含在内)放入箱子中，恰好装满箱子，而不留下任何空隙，当然，他也可以选择全部用填充物来埴满整个箱子(如果埴充物足够多的话)，也即装满一箱纪念品，小明也觉得很棒!

输入描述

第一行1个整数T，表示数据组数。对于每组数据:

第一行包合三个整数N和n和c，分别表示箱子的容量和玩具的数量以及填充物数量，

第二行包含n个整数a0,a1…an，分别表示这n个玩具的大小。1≤T≤100,1≤n≤500,1≤N,c,ai≤1000

输出描述

输出T行分别表示每组数据答案

对每组数据，输出一行，如果可以恰好装满箱子，输出YES;否则，输出 NO。

样例输入

2

10 4 1

2 3 5 7

10 1 3

6

样例输出

YES

NO

参考题解

背包dp。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<iostream>
#include<vector>
using namespace std;
void solve() {
    int N, n, c;
    cin >> N >> n >> c;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(N + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int x = nums[i - 1];
        for (int j = 0; j <= N; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= x) {
                dp[i][j] |= dp[i - 1][j - x];
            }
        }
    }

    for (int i = 0; i <= N; i++) {
        if (dp[n][i] && i + c >= N) {
            cout << "YES" << "\n";
            return;
        }
    }

    cout << "NO" << "\n";
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Solution {
    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int n = sc.nextInt();
        int c = sc.nextInt();
        
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        boolean[][] dp = new boolean[n + 1][N + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int j = 0; j <= N; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= x) {
                    dp[i][j] |= dp[i - 1][j - x];
                }
            }
        }

        for (int i = 0; i <= N; i++) {
            if (dp[n][i] && i + c >= N) {
                System.out.println("YES");
                return;
            }
        }
        
        System.out.println("NO");
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def solve():
    N, n, c = map(int, input().split())
    nums = list(map(int, input().split()))

    dp = [[0] * (N + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        x = nums[i - 1]
        for j in range(N + 1):
            dp[i]