Fractional Knapsack Algoritması

1type Item = { name: string; value: number; weight: number; };
2function fractionalKnapsack(items: Item[], capacity: number) {
3  const sortedItems = [...items].sort((a, b) => b.value / b.weight - a.value / a.weight);
4  let remaining = capacity, totalValue = 0;
5  const selected: Array = [];
6  for (const item of sortedItems) {
7    if (remaining <= 0) break;
8    const fraction = Math.min(1, remaining / item.weight);
9    selected.push({ ...item, fraction });
10    totalValue += item.value * fraction;
11    remaining -= item.weight * fraction;
12  }
13  return { totalValue, selected };
14}