← 返回 optiver 的题目列表Optimize Cargo Transport Algorithm
类型:online_judge
You are tasked with improving an algorithm used by a transportation company for planning cargo shipping and flight booking. The existing algorithm is not profitable. You have the following information:
You have a list of flights available for booking. Each flight includes: departure time, maximum weight capacity, and cost.
You have a list of cargo available for booking. Each cargo includes: weight, latest required arrival time, and revenue if shipped.
The goal is to write an algorithm that maximizes the overall profit of the transportation plan, which is total revenue minus total cost.
Requirements:
Provide a Python implementation.
Write a class that can process information incrementally.
Be able to extend the implementation based on emerging requirements.
Test cases:
Flight list: [{'departure': 8, 'max_weight': 1000, 'cost': 500}, {'departure': 10, 'max_weight': 2000, 'cost': 800}]
Cargo list: [{'weight': 500, 'latest_arrival': 9, 'revenue': 1000}, {'weight': 1500, 'latest_arrival': 10, 'revenue': 1500}]
Output: Plan with maximum possible profit
Example
Input
航班列表:[{ 'departure': 8, 'max_weight': 1000, 'cost': 500 }, { 'departure': 10, 'max_weight': 2000, 'cost': 800 }]
货物列表:[{ 'weight': 500, 'latest_arrival': 9, 'revenue': 1000 }, { 'weight': 1500, 'latest_arrival': 10, 'revenue': 1500 }]