Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediummeet-in-the-middle

Campus Bikes II

Problem (yeniden ifade)

Her işçiye benzersiz bir bisiklet ata. Toplam Manhattan uzaklığını küçült. workers, bikes ≤ 10.

Sezgi

Bu atama, alt küme-toplamı MITM değil. m ≤ 10 iken 2^m MITM ölçeğinde olduğu için katalog burada listeler; algoritma kullanılan bisikletler üzerinde bitmask DP.

Yaklaşımlar

Bitmask atama DP

Doğrulanmadı

Zaman O(m·2^m)Alan O(2^m)

Fikir. dp[mask] = mask içindeki bisikletlere ilk popcount(mask) işçiyi atamanın min maliyeti. Geçiş: işçi k’ye kullanılmayan bisiklet j. Maskeleri artan sırada gez ki mask | (1<<j) mask’ten sonra yazılsın. Cevap: n bitli maskeler arasında min dp[mask].

Yürüyüş. workers [[0,0],[2,1]], bikes [[1,2],[3,3]] → 6 ((0,0)→(1,2) maliyet 3 artı (2,1)→(3,3) maliyet 3).

Trade-off. n=10’da Hungarian fazla. İşçileri bölmek (gerçek MITM) mümkün ama bu m·2^m DP’den daha dağınık.

Çözüm

export function assignBikes(workers: number[][], bikes: number[][]): number {
  const n = workers.length;
  const m = bikes.length;
  const inf = 1e9;
  const dp = new Array<number>(1 << m).fill(inf);
  dp[0] = 0;
  let ans = inf;
  for (let mask = 0; mask < 1 << m; mask++) {
    const cur = dp[mask]!;
    if (cur >= inf) continue;
    let k = 0;
    for (let t = mask; t > 0; t >>= 1) k += t & 1;
    if (k === n) {
      if (cur < ans) ans = cur;
      continue;
    }
    const w = workers[k]!;
    for (let j = 0; j < m; j++) {
      if (mask & (1 << j)) continue;
      const b = bikes[j]!;
      const cost = Math.abs(w[0]! - b[0]!) + Math.abs(w[1]! - b[1]!);
      const nxt = mask | (1 << j);
      dp[nxt] = Math.min(dp[nxt]!, cur + cost);
    }
  }
  return ans;
}

export function assignBikes(workers: number[][], bikes: number[][]): number {
  const n = workers.length;
  const m = bikes.length;
  const inf = 1e9;
  const dp = new Array<number>(1 << m).fill(inf);
  dp[0] = 0;
  let ans = inf;
  for (let mask = 0; mask < 1 << m; mask++) {
    const cur = dp[mask]!;
    if (cur >= inf) continue;
    let k = 0;
    for (let t = mask; t > 0; t >>= 1) k += t & 1;
    if (k === n) {
      if (cur < ans) ans = cur;
      continue;
    }
    const w = workers[k]!;
    for (let j = 0; j < m; j++) {
      if (mask & (1 << j)) continue;
      const b = bikes[j]!;
      const cost = Math.abs(w[0]! - b[0]!) + Math.abs(w[1]! - b[1]!);
      const nxt = mask | (1 << j);
      dp[nxt] = Math.min(dp[nxt]!, cur + cost);
    }
  }
  return ans;
}

Şablon bağlantısı

Atama / TSP tarzı bitmask DP. Katalogda MITM altında yalnızca 2^m MITM ölçeğinde olduğu için; yarıya böl-birleştir yok.

Yansıma

dp[mask] ilk popcount(mask) işçiye o bisikletleri vermenin min maliyeti. İşçi k boştaki bisiklet j’yi alır.
Manhattan. Bir bisiklet bir işçi. Maskeler artan sırada; yeni bit eski maskeden sonra yazılır.
İşçi sayısı bisikletten az olabilir. Cevap tam n bitlik maskelerin min’i. n küçük.