Dallanıp Sınırlandırma (Branch and Bound) Algoritması

1// Node definition for Branch and Bound Knapsack
2interface BBNode {
3  level: number;
4  profit: number;
5  weight: number;
6  bound: number;
7}
8
9function getBound(node: BBNode, n: number, W: number, p: number[], w: number[]): number {
10  if (node.weight >= W) return 0;
11  
12  let profitBound = node.profit;
13  let j = node.level + 1;
14  let totweight = node.weight;
15  
16  while (j < n && totweight + w[j] <= W) {
17    totweight += w[j];
18    profitBound += p[j];
19    j++;
20  }
21  
22  if (j < n) {
23    profitBound += (W - totweight) * (p[j] / w[j]);
24  }
25  
26  return profitBound;
27}
28
29export function knapsackBranchAndBound(W: number, w: number[], p: number[], n: number): number {
30  // Sort items by profit/weight ratio in descending order
31  const items = Array.from({ length: n }, (_, i) => ({ w: w[i], p: p[i], r: p[i]/w[i] }))
32    .sort((a, b) => b.r - a.r);
33    
34  const sortedW = items.map(item => item.w);
35  const sortedP = items.map(item => item.p);
36  
37  const queue: BBNode[] = [];
38  const u: BBNode = { level: -1, profit: 0, weight: 0, bound: 0 };
39  u.bound = getBound(u, n, W, sortedP, sortedW);
40  queue.push(u);
41  
42  let maxProfit = 0;
43  
44  while (queue.length > 0) {
45    // FIFO Strategy (shift from array)
46    const t = queue.shift()!;
47    
48    if (t.level === n - 1) continue;
49    
50    const nextLevel = t.level + 1;
51    
52    // Left child: Include the item
53    const withItem: BBNode = {
54      level: nextLevel,
55      profit: t.profit + sortedP[nextLevel],
56      weight: t.weight + sortedW[nextLevel],
57      bound: 0
58    };
59    
60    if (withItem.weight <= W && withItem.profit > maxProfit) {
61      maxProfit = withItem.profit;
62    }
63    
64    withItem.bound = getBound(withItem, n, W, sortedP, sortedW);
65    if (withItem.bound > maxProfit) {
66      queue.push(withItem);
67    }
68    
69    // Right child: Exclude the item
70    const withoutItem: BBNode = {
71      level: nextLevel,
72      profit: t.profit,
73      weight: t.weight,
74      bound: 0
75    };
76    
77    withoutItem.bound = getBound(withoutItem, n, W, sortedP, sortedW);
78    if (withoutItem.bound > maxProfit) {
79      queue.push(withoutItem);
80    }
81  }
82  
83  return maxProfit;
84}