Knapsack ve Alt Küme DP

Nasıl düşünülür

dp[c] = kapasite c ile en iyi değer (veya erişilebilir bool). 0/1 için kapasiteyi aşağı tara ki her öğe bir kez kullanılsın. Sınırsız için yukarı tara. Alt küme-toplamı value=weight ve bool OR knapsack’tır.

Şablon şekilleri

Şekil	Temel hamle	Notlar
0/1 knapsack	c = W..w	dp[c]=max(dp[c], dp[c-w]+v)
Sınırsız	c = w..W	Coin, kombinasyon
Alt küme toplam	bool dp	Bölüm / hedef

Karmaşıklık temeli

Klasik knapsack O(n·W) zaman ve O(W) alan.

Şablondan probleme

1. 0/1 vs sınırsız ayırt et.
2. Kapasite W koy (sıkça sum/2).
3. dp[0]=0 veya true; öğe başına doldur.
4. dp[W] veya yol sayısını oku.

/** Knapsack template: partition equal subset sum (0/1 bool DP). */
export function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2) return false;
  const target = sum / 2;
  const dp = new Array<boolean>(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    for (let c = target; c >= x; c--) dp[c] = dp[c]! || dp[c - x]!;
  }
  return dp[target]!;
}

/** Knapsack template: partition equal subset sum (0/1 bool DP). */
export function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2) return false;
  const target = sum / 2;
  const dp = new Array<boolean>(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    for (let c = target; c >= x; c--) dp[c] = dp[c]! || dp[c - x]!;
  }
  return dp[target]!;
}