【NOIP普及组】 装箱问题

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

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

输入

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

输出

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

样例输入

24
6
8
3
12
7
9
7

样例输出

0 

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++实现的代码：

#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); // 输出箱子剩余空间}
}

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