1免费做网站,行业开发,网页游戏开服表大全,沈阳定制网络机箱机柜【NOIP普及组】 装箱问题 #x1f490;The Begin#x1f490;点点关注#xff0c;收藏不迷路#x1f490; 有一个箱子容量为V#xff08;正整数#xff0c;0#xff1c;#xff1d;V#xff1c;#xff1d;20000#xff09;#xff0c;同时有n个物品#xff08;0The Begin点点关注收藏不迷路
有一个箱子容量为V正整数0V20000同时有n个物品0n30每个物品有一个体积正整数。 要求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::vectorint 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::vectorint 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点点关注收藏不迷路
