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

题目描述

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

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

输入描述

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

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

输出描述

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

备注

不需要考虑异常输入

用例

题目解析

本题可以转化为01背包问题。

关于01背包问题可以看：

关于01背包滚动数组优化：算法设计 – 01背包问题的状态转移方程优化，以及完全背包问题_01背包问题状态转移方程_伏城之外的博客-CSDN博客

本题中：

货车的载重量 → 背包承重

物品 → 快递

物品种类  → 快递重量

物品价值  → 1（件数）

这里要求货车能装最多快递件数，其实相当于每件物品的价值为1，求解01背包问题的最大价值。

2023.06.18

本题之前想复杂了，其实本题需要：装最多件数，但是不能超载

因此，我们应该尽量选择重量小的快递。

因此，可以将输入的快递重量数组进行升序，依次累加，看总重量是否超过限制即可，超过限制，则对应快递不能加入，最多只能运送前面所有快递。

其实，这里很容易理解，假设0~i的快递总重量都在限载内，那么下一个快递我们最优是选择什么呢？

当然是选择重量最小的加入尝试。

因此，每次我们选择加入的都是重量最小的，才能保证结果最优。此解法为贪心解法。

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("%dn", 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;
}