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

(100分)- 快递运输Java JS Python C题目描述一辆运送快递的货车运送的快递放在大小不等的长方体快递盒中为了能够装载更多的快递同时不能让货车超载需要计算最多能装多少个快递。注快递的体积不受限制快递数最多1000个货车载重最大50000输入描述第一行输入每个快递的重量用英文逗号隔开如 5,10,2,11第二行输入货车的载重量如 20输出描述输出最多能装多少个快递如 3备注不需要考虑异常输入用例输入5,10,2,1120输出3说明货车的载重量为20最多只能放三个快递5、10、2因此输出3题目解析这个问题可以建模为经典的01背包问题核心对应关系如下货车的载重量 → 背包的最大承重快递物品 → 待装入背包的物品快递重量 → 物品的重量每件快递 → 价值为1的单位物品解题目标转化为在不超过货车载重的前提下选择尽可能多的快递相当于在01背包问题中求取价值最大化每件物品价值均为1时的最优解。这道题的关键在于运送尽可能多的快递而不超载。解决思路如下将快递按重量从小到大排序从最轻的快递开始依次累加当累加重量超过限载时停止此时已装载的快递数量即为最大值这种贪心算法的正确性在于要最大化快递数量就应该优先选择重量最小的每一步都选择当前最优解最轻的快递最终就能得到全局最优解最多快递数量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; }