Thuật toán tham lam (Greedy Algorithm)

def activity_selection(activities):
    """Chọn nhiều hoạt động nhất không chồng chéo"""
    activities.sort(key=lambda x: x[1])  # Sort by end time
    
    result = [activities[0]]
    last_end = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end:
            result.append((start, end))
            last_end = end
    
    return result

fun activitySelection(activities: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    val sorted = activities.sortedBy { it.second }
    val result = mutableListOf(sorted[0])
    var lastEnd = sorted[0].second
    
    for ((start, end) in sorted.drop(1)) {
        if (start >= lastEnd) {
            result.add(Pair(start, end))
            lastEnd = end
        }
    }
    return result
}

List<List<int>> activitySelection(List<List<int>> activities) {
  activities.sort((a, b) => a[1].compareTo(b[1]));
  
  List<List<int>> result = [activities[0]];
  int lastEnd = activities[0][1];
  
  for (var activity in activities.skip(1)) {
    if (activity[0] >= lastEnd) {
      result.add(activity);
      lastEnd = activity[1];
    }
  }
  return result;
}

func activitySelection(_ activities: [(Int, Int)]) -> [(Int, Int)] {
    let sorted = activities.sorted { $0.1 < $1.1 }
    var result = [sorted[0]]
    var lastEnd = sorted[0].1
    
    for (start, end) in sorted.dropFirst() {
        if start >= lastEnd {
            result.append((start, end))
            lastEnd = end
        }
    }
    return result
}

List<int[]> activitySelection(List<int[]> activities) {
    activities.sort(Comparator.comparingInt(a -> a[1]));
    
    List<int[]> result = new ArrayList<>();
    result.add(activities.get(0));
    int lastEnd = activities.get(0)[1];
    
    for (int i = 1; i < activities.size(); i++) {
        if (activities.get(i)[0] >= lastEnd) {
            result.add(activities.get(i));
            lastEnd = activities.get(i)[1];
        }
    }
    return result;
}

def fractional_knapsack(items, capacity):
    """items = [(weight, value), ...]"""
    # Sort by value/weight ratio
    items.sort(key=lambda x: x[1] / x[0], reverse=True)
    
    total_value = 0
    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break
    
    return total_value

fun fractionalKnapsack(items: List<Pair<Int, Int>>, cap: Int): Double {
    val sorted = items.sortedByDescending { it.second.toDouble() / it.first }
    var capacity = cap.toDouble()
    var totalValue = 0.0
    
    for ((weight, value) in sorted) {
        if (capacity >= weight) {
            capacity -= weight
            totalValue += value
        } else {
            totalValue += value * (capacity / weight)
            break
        }
    }
    return totalValue
}

double fractionalKnapsack(List<List<int>> items, int cap) {
  items.sort((a, b) => (b[1] / b[0]).compareTo(a[1] / a[0]));
  
  double capacity = cap.toDouble();
  double totalValue = 0;
  
  for (var item in items) {
    if (capacity >= item[0]) {
      capacity -= item[0];
      totalValue += item[1];
    } else {
      totalValue += item[1] * (capacity / item[0]);
      break;
    }
  }
  return totalValue;
}

func fractionalKnapsack(_ items: [(Int, Int)], _ cap: Int) -> Double {
    let sorted = items.sorted { Double($0.1) / Double($0.0) > Double($1.1) / Double($1.0) }
    var capacity = Double(cap)
    var totalValue = 0.0
    
    for (weight, value) in sorted {
        if capacity >= Double(weight) {
            capacity -= Double(weight)
            totalValue += Double(value)
        } else {
            totalValue += Double(value) * (capacity / Double(weight))
            break
        }
    }
    return totalValue
}

double fractionalKnapsack(int[][] items, int cap) {
    Arrays.sort(items, (a, b) -> 
        Double.compare((double)b[1]/b[0], (double)a[1]/a[0]));
    
    double capacity = cap;
    double totalValue = 0;
    
    for (int[] item : items) {
        if (capacity >= item[0]) {
            capacity -= item[0];
            totalValue += item[1];
        } else {
            totalValue += item[1] * (capacity / item[0]);
            break;
        }
    }
    return totalValue;
}