Çanta Problemi Varyantları (Knapsack Problem Variants) Algoritması

1export function unboundedKnapsack(W: number, w: number[], v: number[], n: number): number {
2  const dp = new Array(W + 1).fill(0);
3  
4  for (let weight = 1; weight <= W; weight++) {
5    for (let i = 0; i < n; i++) {
6      if (w[i] <= weight) {
7        dp[weight] = Math.max(dp[weight], dp[weight - w[i]] + v[i]);
8      }
9    }
10  }
11  return dp[W];
12}
13
14export function boundedKnapsack(W: number, w: number[], v: number[], c: number[], n: number): number {
15  // Convert Bounded to 0/1 Knapsack using binary decomposition
16  const newW: number[] = [];
17  const newV: number[] = [];
18  
19  for (let i = 0; i < n; i++) {
20    let limit = c[i];
21    let k = 1;
22    while (limit > 0) {
23      const take = Math.min(k, limit);
24      newW.push(take * w[i]);
25      newV.push(take * v[i]);
26      limit -= take;
27      k *= 2;
28    }
29  }
30  
31  // Standard 0/1 DP
32  const m = newW.length;
33  const dp = new Array(W + 1).fill(0);
34  for (let i = 0; i < m; i++) {
35    for (let weight = W; weight >= newW[i]; weight--) {
36      dp[weight] = Math.max(dp[weight], dp[weight - newW[i]] + newV[i]);
37    }
38  }
39  return dp[W];
40}