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

Mediumknapsack-subset-dp

Ones and Zeroes

Problem (yeniden ifade)

İkili dizgiler strs; m sıfır ve n bir bütçesi. Bütçeleri aşmadan oluşturulabilecek en büyük dizgi alt kümesi.

Sezgi

Her dizgi maliyeti (sıfır, bir) ve değeri 1 olan bir eşya. Klasik 0/1 knapsack, 2D kapasite.

Yaklaşımlar

2D 0/1 knapsack

Doğrulanmadı

Zaman O(L·m·n)Alan O(m·n)

Fikir. dp[i][j] = ≤i sıfır ve ≤j bir ile max dizgi. Eşyaları kapasiteler üzerinde tersten iterasyonla işle.

Yürüyüş. strs=[“10”,“0001”,“111001”,“1”,“0”], m=5,n=3 → 4.

Trade-off. İleri döngüler aynı dizgiyi yeniden kullanır; ters yön 0/1’i zorlar.

Çözüm

export function findMaxForm(strs: string[], m: number, n: number): number {
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0, ones = 0;
    for (const c of s) if (c === "0") zeros++; else ones++;
    for (let i = m; i >= zeros; i--) {
      for (let j = n; j >= ones; j--) {
        dp[i]![j] = Math.max(dp[i]![j]!, dp[i - zeros]![j - ones]! + 1);
      }
    }
  }
  return dp[m]![n]!;
}

export function findMaxForm(strs: string[], m: number, n: number): number {
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0, ones = 0;
    for (const c of s) if (c === "0") zeros++; else ones++;
    for (let i = m; i >= zeros; i--) {
      for (let j = n; j >= ones; j--) {
        dp[i]![j] = Math.max(dp[i]![j]!, dp[i - zeros]![j - ones]! + 1);
      }
    }
  }
  return dp[m]![n]!;
}

Şablon bağlantısı

Çok boyutlu kapasiteli 0/1 knapsack.

Yansıma

Her dizgi bir kez. m ve n döngüleri geriye. dp[z][o] o bütçeyle en çok dizgi.
İleri döngü aynı dizgiyi tekrar sayar. 0 ve 1 sayısı bütçeyi aşan dizgi atlanır.
m = n = 0: boş dizgi varsa 1. Boş liste 0.