#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    int start, end;
    int weight; // 用于加权版本
    
    Interval(int s, int e, int w = 1) : start(s), end(e), weight(w) {}
};

class IntervalScheduling {
public:
    // 经典区间调度 - 最大不重叠区间数
    static int maxIntervals(vector<Interval>& intervals) {
        if (intervals.empty()) return 0;
        
        // 按结束时间排序
        sort(intervals.begin(), intervals.end(), 
             [](const Interval& a, const Interval& b) {
                 return a.end < b.end;
             });
        
        int count = 1;
        int lastEnd = intervals[0].end;
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i].start >= lastEnd) {
                count++;
                lastEnd = intervals[i].end;
            }
        }
        
        return count;
    }
    
    // 加权区间调度的贪心近似
    static int maxWeightGreedy(vector<Interval>& intervals) {
        if (intervals.empty()) return 0;
        
        // 按权重/长度比排序（贪心启发式）
        sort(intervals.begin(), intervals.end(), 
             [](const Interval& a, const Interval& b) {
                 double ratioA = (double)a.weight / (a.end - a.start);
                 double ratioB = (double)b.weight / (b.end - b.start);
                 return ratioA > ratioB;
             });
        
        int totalWeight = 0;
        vector<bool> used(intervals.size(), false);
        
        for (int i = 0; i < intervals.size(); i++) {
            if (used[i]) continue;
            
            totalWeight += intervals[i].weight;
            used[i] = true;
            
            // 标记重叠区间为已使用
            for (int j = i + 1; j < intervals.size(); j++) {
                if (!used[j] && intervalsOverlap(intervals[i], intervals[j])) {
                    used[j] = true;
                }
            }
        }
        
        return totalWeight;
    }
    
    // 覆盖一个点的最少区间数
    static int minIntervalsToPoint(vector<Interval>& intervals, int point) {
        vector<Interval> covering;
        
        // 找覆盖该点的区间
        for (const auto& interval : intervals) {
            if (interval.start <= point && point <= interval.end) {
                covering.push_back(interval);
            }
        }
        
        if (covering.empty()) return -1; // 不可能
        
        // 按开始时间排序，然后按结束时间
        sort(covering.begin(), covering.end(), 
             [](const Interval& a, const Interval& b) {
                 if (a.start != b.start) return a.start < b.start;
                 return a.end > b.end;
             });
        
        return 1; // 至少有一个区间覆盖该点
    }
    
private:
    static bool intervalsOverlap(const Interval& a, const Interval& b) {
        return !(a.end <= b.start || b.end <= a.start);
    }
};

int main() {
    vector<Interval> intervals = {
        Interval(1, 3, 5), Interval(2, 5, 8), Interval(3, 6, 3),
        Interval(4, 7, 6), Interval(5, 8, 4), Interval(6, 9, 7)
    };
    
    cout << "区间 (开始, 结束, 权重):" << endl;
    for (const auto& interval : intervals) {
        cout << "(" << interval.start << ", " << interval.end << ", " << interval.weight << ") ";
    }
    cout << endl;
    
    // 测试经典区间调度
    vector<Interval> copy1 = intervals;
    int maxCount = IntervalScheduling::maxIntervals(copy1);
    cout << "\n最大不重叠区间数: " << maxCount << endl;
    
    // 测试加权区间调度
    vector<Interval> copy2 = intervals;
    int maxWeight = IntervalScheduling::maxWeightGreedy(copy2);
    cout << "最大权重（贪心近似）: " << maxWeight << endl;
    
    // 测试点覆盖
    int point = 4;
    vector<Interval> copy3 = intervals;
    int minCover = IntervalScheduling::minIntervalsToPoint(copy3, point);
    cout << "点 " << point << " 可以被 " << minCover << " 个区间覆盖" << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Item {
    int value, weight;
    double ratio;
    int index;
    
    Item(int v, int w, int idx) : value(v), weight(w), index(idx) {
        ratio = (double)value / weight;
    }
};

class FractionalKnapsack {
public:
    struct Solution {
        double maxValue;
        vector<double> fractions; // 每个物品取的比例
        
        Solution(int n) : maxValue(0), fractions(n, 0) {}
    };
    
    static Solution solve(vector<Item>& items, int capacity) {
        int n = items.size();
        Solution solution(n);
        
        // 按价值重量比降序排序
        sort(items.begin(), items.end(), 
             [](const Item& a, const Item& b) {
                 return a.ratio > b.ratio;
             });
        
        int remainingCapacity = capacity;
        
        for (const auto& item : items) {
            if (remainingCapacity >= item.weight) {
                // 取整个物品
                solution.fractions[item.index] = 1.0;
                solution.maxValue += item.value;
                remainingCapacity -= item.weight;
            } else if (remainingCapacity > 0) {
                // 取物品的一部分
                double fraction = (double)remainingCapacity / item.weight;
                solution.fractions[item.index] = fraction;
                solution.maxValue += item.value * fraction;
                remainingCapacity = 0;
                break;
            }
        }
        
        return solution;
    }
    
    // 变体：多个背包
    static vector<Solution> multipleKnapsacks(vector<Item>& items, vector<int>& capacities) {
        vector<Solution> solutions;
        
        // 按比率排序物品
        sort(items.begin(), items.end(), 
             [](const Item& a, const Item& b) {
                 return a.ratio > b.ratio;
             });
        
        for (int capacity : capacities) {
            vector<Item> availableItems = items; // 为这个背包复制
            Solution solution = solve(availableItems, capacity);
            solutions.push_back(solution);
        }
        
        return solutions;
    }
};

// 带时间约束的连续背包
class TimeConstrainedKnapsack {
public:
    struct Task {
        int value, time;
        double efficiency;
        int index;
        
        Task(int v, int t, int idx) : value(v), time(t), index(idx) {
            efficiency = (double)value / time;
        }
    };
    
    static double maxValueInTime(vector<Task>& tasks, int totalTime) {
        // 按效率排序（单位时间价值）
        sort(tasks.begin(), tasks.end(), 
             [](const Task& a, const Task& b) {
                 return a.efficiency > b.efficiency;
             });
        
        double maxValue = 0;
        int remainingTime = totalTime;
        
        for (const auto& task : tasks) {
            if (remainingTime >= task.time) {
                maxValue += task.value;
                remainingTime -= task.time;
            } else if (remainingTime > 0) {
                // 部分任务完成
                double fraction = (double)remainingTime / task.time;
                maxValue += task.value * fraction;
                break;
            }
        }
        
        return maxValue;
    }
};

int main() {
    // 测试分数背包
    vector<Item> items = {
        Item(60, 10, 0), Item(100, 20, 1), Item(120, 30, 2)
    };
    int capacity = 50;
    
    cout << "物品 (价值, 重量, 比率):" << endl;
    for (const auto& item : items) {
        cout << "Item " << item.index << ": (" << item.value << ", " << item.weight 
             << ", " << fixed << setprecision(2) << item.ratio << ")" << endl;
    }
    
    FractionalKnapsack::Solution solution = FractionalKnapsack::solve(items, capacity);
    
    cout << "\n背包容量: " << capacity << endl;
    cout << "最大价值: " << fixed << setprecision(2) << solution.maxValue << endl;
    cout << "物品取用比例:" << endl;
    for (int i = 0; i < solution.fractions.size(); i++) {
        if (solution.fractions[i] > 0) {
            cout << "Item " << i << ": " << fixed << setprecision(2) 
                 << solution.fractions[i] * 100 << "%" << endl;
        }
    }
    
    // 测试时间约束任务
    vector<TimeConstrainedKnapsack::Task> tasks = {
        TimeConstrainedKnapsack::Task(100, 20, 0),
        TimeConstrainedKnapsack::Task(60, 10, 1),
        TimeConstrainedKnapsack::Task(140, 40, 2)
    };
    int totalTime = 50;
    
    cout << "\n任务 (价值, 时间, 效率):" << endl;
    for (const auto& task : tasks) {
        cout << "Task " << task.index << ": (" << task.value << ", " << task.time 
             << ", " << fixed << setprecision(2) << task.efficiency << ")" << endl;
    }
    
    double maxTaskValue = TimeConstrainedKnapsack::maxValueInTime(tasks, totalTime);
    cout << "\n在 " << totalTime << " 时间单位内的最大价值: " 
         << fixed << setprecision(2) << maxTaskValue << endl;
    
    return 0;
}