仓储中心货物装箱

题意

有 个集装箱，每个集装箱有最大载重量。有 件货物，每件有重量。一个集装箱可以装多件货物，但总重量不能超过载重限制。货物不可分割，必须完整装入一个集装箱。问最多能装多少件货物。

思路

要装尽可能多的货物，直觉上应该优先装轻的——轻货物占的"重量配额"少，同样的容量能塞更多件。这就是贪心的核心。

具体做法：

  1. 把货物按重量从小到大排序，把集装箱按容量从小到大排序。
  2. 依次考虑每个集装箱（从最小的开始），尽量往里塞当前最轻的货物，直到装不下为止，再换下一个集装箱继续。

为什么集装箱也要从小到大？因为轻货物用小集装箱就够了，把大集装箱留给后面可能更重的货物，不会浪费容量。

为什么这个贪心是对的？

假设存在一个最优解装了 件货物，但选的不全是最轻的 件。那我们把其中任意一件替换成更轻的那件，容量只会更宽裕，方案依然合法。所以最优解一定可以调整为"选最轻的 件"。

选定了最轻的 件之后，按重量从小到大依次往最小的能装下的集装箱里塞，这个分配方式不会比任何其他分配方式差——小集装箱能装的就不浪费大集装箱的空间。

拿样例验证：集装箱容量排序后为 ，货物重量排序后为 。从最小集装箱开始装最轻货物：容量 1 装不下 9，容量 2 也装不下 9，容量 14 装 9（剩 5，下一件 14 装不下），容量 15 装 14（剩 1），容量 22 装 14（剩 8），容量 32 装 17（剩 15），容量 50 装 25（剩 25），容量 50 装 32（剩 18）。一共装了 6 件，和答案一致。

复杂度

  • 时间：，排序主导
  • 空间：

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    vector<int> cap(n);
    for(int i=0;i<n;i++) scanf("%d",&cap[i]);
    int m;
    scanf("%d",&m);
    vector<int> w(m);
    for(int i=0;i<m;i++) scanf("%d",&w[i]);

    sort(cap.begin(), cap.end());
    sort(w.begin(), w.end());

    int ptr = 0, ans = 0;
    for(int i=0;i<n && ptr<m;i++){
        int remain = cap[i];
        while(ptr < m && w[ptr] <= remain){
            remain -= w[ptr];
            ptr++;
            ans++;
        }
    }

    printf("%d\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] cap = new int[n];
        for (int i = 0; i < n; i++) cap[i] = sc.nextInt();
        int m = sc.nextInt();
        int[] w = new int[m];
        for (int i = 0; i < m; i++) w[i] = sc.nextInt();

        Arrays.sort(cap);
        Arrays.sort(w);

        int ptr = 0, ans = 0;
        for (int i = 0; i < n && ptr < m; i++) {
            int remain = cap[i];
            while (ptr < m && w[ptr] <= remain) {
                remain -= w[ptr];
                ptr++;
                ans++;
            }
        }

        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
cap = list(map(int, input().split()))
m = int(input())
w = list(map(int, input().split()))

cap.sort()
w.sort()

ptr = 0
ans = 0
for i in range(n):
    if ptr >= m:
        break
    remain = cap[i]
    while ptr < m and w[ptr] <= remain:
        remain -= w[ptr]
        ptr += 1
        ans += 1

print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const cap = lines[1].split(' ').map(Number);
    const m = parseInt(lines[2]);
    const w = lines[3].split(' ').map(Number);

    cap.sort((a, b) => a - b);
    w.sort((a, b) => a - b);

    let ptr = 0, ans = 0;
    for (let i = 0; i < n && ptr < m; i++) {
        let remain = cap[i];
        while (ptr < m && w[ptr] <= remain) {
            remain -= w[ptr];
            ptr++;
            ans++;
        }
    }

    console.log(ans);
});