この問題は貪欲法により解くことができます。 耐荷重の降順に台車を調べ、「まだ台車に載せられていない荷物のうち、その台車に割り当て可能な最も重い荷物」を割り当てることで最適解が得られることを示します。

証明

貪欲法により定まる割り当てと異なる割り当て \(X\) を任意に1つ取ります。このとき、貪欲法による割り当てと異なる台車のうち、耐荷重が最大のものを考え、それを台車 \(i\) とします。

割り当て \(X\) を適切に変更することで、解を悪化させることなく、台車 \(i\) に割り当てられる荷物を貪欲法と一致させられることを示します。これを示すことができれば、\(i\) に関する帰納法により貪欲法が最適であることが示せます。

以下では、荷物が割り当てられていない台車には重さ0の荷物が割り当てられているものとし、台車に割り当てられていない荷物は仮想的な台車に割り当てられているものとみなします。

仮定より、台車 \(i\) より耐荷重が大きいすべての台車では、割り当て \(X\) と貪欲法の割り当ては一致しています。台車 \(i\) については、貪欲法では荷物 \(p\) を割り当てているのに対し、割り当て \(X\) ではそれ以下の重さの荷物 \(q\) が割り当てられています。（貪欲法の定義より）

割り当て \(X\) において荷物 \(p\) が割り当てられている台車を \(j\) とします。貪欲法において荷物 \(p\) は台車 \(i\) に割り当て可能であり、また荷物 \(q\) の重さは荷物 \(p\) 以下なので、荷物 \(p\) を割り当てている台車 \(j\) は代わりに荷物 \(q\) を割り当てることが可能です。

したがって、台車 \(i\) に \(p\)、台車 \(j\) に \(q\) を割り当てるように入れ替えることができ、損をしません。

実装

「まだ台車に載せられていない荷物のうち、その台車に割り当て可能な最も重い荷物を割り当てる」という操作は、荷物を降順に見て「載せられるなら載せ、載せられないなら捨てて次を見る」を繰り返すことで実現できます。

よって、台車を耐荷重の降順、荷物を荷物の降順にソートすることで、 \(O(N\log N)\) 時間でこの問題を解くことができます。

実装例 (C++)

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

int main(){
  int n;
  cin >> n;
  vector<int>w(n),c(n);
  for(int i=0; i<n; i++) cin >> w[i];
  for(int i=0; i<n; i++) cin >> c[i];
  sort(w.rbegin(), w.rend());
  sort(c.rbegin(), c.rend());

  int pos = 0;
  int ans = 0;
  for(int i=0; i<n; i++){
    while(pos < n && w[pos] > c[i]){
      pos++;
    }
    if(pos != n){
      ans++;
      pos++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N = int(input())
W = list(map(int, input().split()))
C = list(map(int, input().split()))
W.sort(reverse=True)
C.sort(reverse=True)

pos = 0
ans = 0
for c in C:
  while pos < N and W[pos] > c:
    pos += 1
  if pos != N:
    ans += 1
    pos += 1

print(ans)