题目链接

仓储中心货物装箱

题目描述

给定一个代表集装箱载重的数组 capacities 和一个代表货物重量的数组 weights。一个集装箱内可以装入多件货物，只要总重量不超过其载重。但由于货物不可分割，一件货物必须完整地装入一个集装箱。

你需要找出一种装箱方案，使得能够被成功装箱的货物数量最多。

输入:

  • 集装箱数量 和各自的载重量。
  • 货物数量 和各自的重量。

输出:

  • 一个整数，表示最多可以成功装箱的货物数量。

解题思路

这个问题需要我们最大化装入集装箱的货物数量，且每个集装箱可以装载多件货物。这是一个典型的贪心问题。

核心思想：为了装下尽可能多的货物，我们应该优先使用最小的货物去填充最小的集装箱。

  1. 排序

    • 对货物重量 weights 和集装箱容量 capacities 都进行 升序 排序。
    • 排序货物是为了确保我们总是优先考虑最轻的、最容易装箱的货物。
    • 排序集装箱是为了确保我们总是优先使用容量最小的、最受限的资源，从而为更重的货物保留更大的集装箱。

  2. 贪心填充 (双指针法)

    • 我们使用两个指针：item_idx 指向当前待装箱的最轻的货物，container_idx 指向当前待填充的最小的集装箱。
    • 外层循环遍历每一个集装箱（从小到大）。
    • 对于当前的集装箱，内层循环尝试用当前可用的、最轻的货物去填充它，直到装满或者没有更小的货物能装下为止。
    • 由于两个数组都已排序，item_idx 指针在整个过程中只需要向前移动，不需要回溯。

  3. 算法流程

    • 初始化 item_idx = 0。最终装箱的货物数量就是 item_idx 的值。
    • 遍历 capacities 数组中的每个 capacity：
      • 创建一个变量 current_capacity 记录当前集装箱的剩余容量。
      • 当 item_idx 未越界且 weights[item_idx] <= current_capacity 时，循环：
        • 将当前货物装入：current_capacity -= weights[item_idx]。
        • 移动货物指针：item_idx++，表示该货物已被装箱。

  4. 终止

    • 遍历完所有集装箱后，item_idx 的值即为最终答案。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n_containers;
    cin >> n_containers;
    vector<long long> capacities(n_containers);
    for (int i = 0; i < n_containers; ++i) {
        cin >> capacities[i];
    }

    int n_items;
    cin >> n_items;
    vector<int> weights(n_items);
    for (int i = 0; i < n_items; ++i) {
        cin >> weights[i];
    }

    sort(capacities.begin(), capacities.end());
    sort(weights.begin(), weights.end());

    int item_ptr = 0;
    for (int i = 0; i < n_containers; ++i) {
        long long current_capacity = capacities[i];
        while (item_ptr < n_items && weights[item_ptr] <= current_capacity) {
            current_capacity -= weights[item_ptr];
            item_ptr++;
        }
    }

    cout << item_ptr << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int nContainers = sc.nextInt();
        long[] capacities = new long[nContainers];
        for (int i = 0; i < nContainers; i++) {
            capacities[i] = sc.nextLong();
        }

        int nItems = sc.nextInt();
        int[] weights = new int[nItems];
        for (int i = 0; i < nItems; i++) {
            weights[i] = sc.nextInt();
        }

        Arrays.sort(capacities);
        Arrays.sort(weights);

        int itemPtr = 0;
        for (int i = 0; i < nContainers; i++) {
            long currentCapacity = capacities[i];
            while (itemPtr < nItems && weights[itemPtr] <= currentCapacity) {
                currentCapacity -= weights[itemPtr];
                itemPtr++;
            }
        }

        System.out.println(itemPtr);
    }
}

def main():
    n_containers = int(input())
    capacities = list(map(int, input().split()))
    
    n_items = int(input())
    weights = list(map(int, input().split()))

    capacities.sort()
    weights.sort()

    item_ptr = 0
    for capacity in capacities:
        current_capacity = capacity
        while item_ptr < n_items and weights[item_ptr] <= current_capacity:
            current_capacity -= weights[item_ptr]
            item_ptr += 1
            
    print(item_ptr)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心、排序、双指针
  • 时间复杂度：，其中 是集装箱数量， 是货物数量。算法的瓶颈在于对两个数组的排序。排序后的双指针遍历过程是线性的，时间复杂度为 。
  • 空间复杂度： 或 ，取决于排序算法所使用的额外栈空间。不考虑输入数组本身占用的空间。