【NOIP普及组】装箱问题

💐The Begin💐点点关注，收藏不迷路💐

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30＝，每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入

第一行，一个整数，表示箱子容量；
第二行，一个整数，表示有n个物品；
接下来n行，分别表示这n个物品的各自体积。

输出

一个整数，表示箱子剩余空间。

样例输入

样例输出

C语言实现的代码：

#include <stdio.h>// 递归函数用于计算最小剩余空间
int pack(int capacity, int* items, int index, int n) {// 如果箱子容量为 0 或者已经考虑完所有物品，返回箱子容量if (capacity == 0 || index == n) return capacity;// 如果当前物品体积大于箱子容量，直接考虑下一个物品if (items[index] > capacity) return pack(capacity, items, index + 1, n);// 尝试放入当前物品和不放入当前物品，取剩余空间较小的情况return (capacity - items[index] >= 0)? (int)fmin(pack(capacity - items[index], items, index + 1, n), pack(capacity, items, index + 1, n)) : pack(capacity, items, index + 1, n);
}int main() {int capacity;scanf("%d", &capacity); // 输入箱子容量int n;scanf("%d", &n); // 输入物品数量int items[n];for (int i = 0; i < n; ++i) {scanf("%d", &items[i]); // 输入每个物品的体积}int result = pack(capacity, items, 0, n); // 调用函数计算最小剩余空间printf("%d\n", result); // 输出箱子剩余空间return 0;
}

在这里插入图片描述
以下是对这段 C 语言代码的解析：

一、整体功能概述

这段代码的目的是解决装箱问题，即给定一个箱子的容量和若干物品的体积，通过选择放入一些物品，使得箱子的剩余空间最小。

二、函数解析

pack函数：
- 这是一个递归函数，用于计算箱子的最小剩余空间。
- 如果箱子容量为 0 或者已经考虑完所有物品（即索引达到物品总数n），则直接返回当前的箱子容量。
- 如果当前物品的体积大于箱子容量，那么不放入该物品，直接递归考虑下一个物品，即调用pack(capacity, items, index + 1, n)。
- 如果当前物品的体积不大于箱子容量，那么有两种选择：放入当前物品，然后递归考虑剩余容量和下一个物品，即pack(capacity - items[index], items, index + 1, n)；或者不放入当前物品，直接递归考虑下一个物品，即pack(capacity, items, index + 1, n)。最后取这两种情况中剩余空间较小的结果。
main函数：
- 首先从用户输入读取箱子的容量capacity。
- 接着读取物品的数量n。
- 创建一个大小为n的整数数组items来存储每个物品的体积。通过循环从用户输入读取每个物品的体积并存入数组。
- 调用pack函数，传入箱子容量、物品数组、起始索引 0 和物品总数n，计算最小剩余空间并将结果赋值给result。
- 最后输出箱子的剩余空间result。

三、时间复杂度和空间复杂度分析

时间复杂度：
- 时间复杂度取决于物品的数量和箱子的容量。在最坏情况下，时间复杂度为指数级别，因为对于每个物品都有两种选择（放入或不放入），如果物品数量为n，箱子容量为V，那么时间复杂度大致为 $O(2^n)$ 。
空间复杂度：
- 空间复杂度主要取决于递归调用栈的深度。在最坏情况下，递归调用栈的深度可能达到物品数量n，所以空间复杂度为 $O (n)$ 。

总的来说，这个算法虽然直观，但对于较大规模的输入可能效率较低。可以考虑使用动态规划等更高效的算法来解决装箱问题。

C++实现的代码：

#include <iostream>
#include <vector>// 递归函数用于计算最小剩余空间
int pack(int capacity, const std::vector<int>& items, int index) {// 如果箱子容量为 0 或者已经考虑完所有物品，返回箱子容量if (capacity == 0 || index == items.size()) return capacity;// 如果当前物品体积大于箱子容量，直接考虑下一个物品if (items[index] > capacity) return pack(capacity, items, index + 1);// 尝试放入当前物品和不放入当前物品，取剩余空间较小的情况return std::min(pack(capacity - items[index], items, index + 1), pack(capacity, items, index + 1));
}int main() {int capacity;std::cin >> capacity; // 输入箱子容量int n;std::cin >> n; // 输入物品数量std::vector<int> items(n);for (int i = 0; i < n; ++i) {std::cin >> items[i]; // 输入每个物品的体积}int result = pack(capacity, items, 0); // 调用函数计算最小剩余空间std::cout << result << std::endl; // 输出箱子剩余空间return 0;
}

Python 实现的代码：

def pack(capacity, items, index):# 如果箱子容量为 0 或者已经考虑完所有物品，返回箱子容量if capacity == 0 or index == len(items):return capacity# 如果当前物品体积大于箱子容量，直接考虑下一个物品if items[index] > capacity:return pack(capacity, items, index + 1)# 尝试放入当前物品和不放入当前物品，取剩余空间较小的情况return min(pack(capacity - items[index], items, index + 1), pack(capacity, items, index + 1))capacity = int(input()) # 输入箱子容量
n = int(input()) # 输入物品数量
items = []
for _ in range(n):items.append(int(input())) # 输入每个物品的体积
result = pack(capacity, items, 0) # 调用函数计算最小剩余空间
print(result) # 输出箱子剩余空间

Java 实现的代码：

import java.util.Scanner;class Main{// 递归方法计算最小剩余空间public static int pack(int capacity, int[] items, int index) {// 如果箱子容量为 0 或者已经考虑完所有物品，返回箱子容量if (capacity == 0 || index == items.length) return capacity;// 如果当前物品体积大于箱子容量，直接考虑下一个物品if (items[index] > capacity) return pack(capacity, items, index + 1);// 尝试放入当前物品和不放入当前物品，取剩余空间较小的情况return Math.min(pack(capacity - items[index], items, index + 1), pack(capacity, items, index + 1));}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int capacity = scanner.nextInt(); // 输入箱子容量int n = scanner.nextInt(); // 输入物品数量int[] items = new int[n];for (int i = 0; i < n; i++) {items[i] = scanner.nextInt(); // 输入每个物品的体积}int result = pack(capacity, items, 0); // 调用函数计算最小剩余空间System.out.println(result); // 输出箱子剩余空间}
}