(100分)- 快递运输（Java JS Python C）

(100分)- 快递运输（Java & JS & Python & C）

题目描述

一辆运送快递的货车，运送的快递放在大小不等的长方体快递盒中，为了能够装载更多的快递，同时不能让货车超载，需要计算最多能装多少个快递。

注：快递的体积不受限制，快递数最多1000个，货车载重最大50000

输入描述

第一行输入每个快递的重量，用英文逗号隔开，如 5,10,2,11

第二行输入货车的载重量，如 20

输出描述

输出最多能装多少个快递，如 3

备注

不需要考虑异常输入

用例

题目解析

这个问题可以建模为经典的01背包问题：

核心对应关系如下：

• 货车的载重量 → 背包的最大承重
• 快递物品 → 待装入背包的物品
• 快递重量 → 物品的重量
• 每件快递 → 价值为1的单位物品

解题目标转化为：在不超过货车载重的前提下，选择尽可能多的快递，相当于在01背包问题中求取价值最大化（每件物品价值均为1时的最优解）。

这道题的关键在于运送尽可能多的快递而不超载。

解决思路如下：

1. 将快递按重量从小到大排序
2. 从最轻的快递开始依次累加
3. 当累加重量超过限载时停止，此时已装载的快递数量即为最大值

这种贪心算法的正确性在于：

• 要最大化快递数量，就应该优先选择重量最小的
• 每一步都选择当前最优解（最轻的快递）
• 最终就能得到全局最优解（最多快递数量）

Java算法源码

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] weights = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray(); int limit = Integer.parseInt(sc.nextLine()); System.out.println(getResult(weights, limit)); } public static int getResult(int[] weights, int limit) { Arrays.sort(weights); int count = 0; int sum = 0; for (int w : weights) { // 每次都选择重量最小的快递加入 sum += w; if (sum > limit) break; count++; } return count; } }

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 2) { const weights = lines[0].split(",").map(Number); const limit = parseInt(lines[1]); console.log(getResult(weights, limit)); lines.length = 0; } }); function getResult(weights, limit) { weights.sort((a, b) => a - b); let count = 0; let sum = 0; for (let w of weights) { sum += w; if (sum > limit) break; count++; } return count; }

Python算法源码

# 输入获取 weights = list(map(int, input().split(","))) limit = int(input()) # 算法入口 def getResult(): weights.sort() total = 0 count = 0 for w in weights: total += w if total > limit: break count += 1 return count # 调用算法 print(getResult())

C算法源码

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 1000 int getResult(int weights[], int weights_size, int limit); int main() { int weights[MAX_SIZE]; int weights_size = 0; while(scanf("%d", &weights[weights_size++])) { if(getchar() != ',') break; } int limit; scanf("%d", &limit); printf("%d\n", getResult(weights, weights_size, limit)); return 0; } int cmp(const void* a, const void* b) { return (*(int*) a) - (*(int*) b); } int getResult(int weights[], int weights_size, int limit) { qsort(weights, weights_size, sizeof(int), cmp); int count = 0; int sum = 0; for(int i = 0; i < weights_size; i++) { sum += weights[i]; if(sum > limit) { break; } count++; } return count; }