## 四、实验要求 ### 1. 设计过程 #### 1.1 背包问题的设计过程 **1. 算法思想理解** * **核心贪心策略**：对于背包问题，最直观的贪心策略是**优先选择单位重量价值最高（即“性价比”最高）的物品**。这个选择在当下看来是能让单位背包容量获得最大价值的局部最优选择。 * **两种问题的区分**： * **背包问题（可分割）**：当一个物品无法完整放入时，可以取其一部分填满背包。 * **0-1背包问题（不可分割）**：当一个物品无法完整放入时，只能放弃该物品。 * **对比方案设计**：为了验证贪心算法在0-1背包问题上的局限性，我额外设计了一个基于**动态规划**的求解函数。动态规划能保证求得0-1背包问题的最优解，可以作为“标准答案”来和贪心算法的结果进行对比。 **2. 流程图设计** 下图描述了贪心算法求解背包问题的通用流程。 ```mermaid graph TD A(开始) --> B("计算所有物品的性价比 v/w"); B --> C("按性价比从高到低排序"); C --> D{"遍历已排序的物品"}; D -- 物品i --> E{"背包剩余容量 > 0?"}; E -- 否 --> Z("结束"); E -- 是 --> F{"物品i能完全放入?"}; F -- 是 --> G("将物品i完全放入背包"); G --> H("更新背包容量和总价值"); H --> D; F -- 否 --> I{"是背包问题(可分割)?"}; I -- 是 --> J("取物品i的一部分填满背包"); J --> H; I -- 否 --> K("放弃物品i"); K --> D; ``` #### 1.2 最短平均等待时间问题的设计过程 **1. 算法思想理解** * **问题转化**：最小化“平均等待时间”等价于最小化“总等待时间”。 * **核心贪心策略**：直觉上，应该让服务时间短的顾客先完成，这样可以尽快减少等待队列的总人数，从而减少后续顾客的等待时间。因此，贪心策略确定为**最短处理时间优先 (Shortest Processing Time First)**。 **2. 流程图设计** ```mermaid graph TD A(开始) --> B("获取n个顾客的服务时间列表 T"); B --> C("对列表T按从小到大排序"); C --> D("初始化总等待时间total_wait = 0, 当前等待时间current_wait = 0"); D --> E("循环遍历排序后的服务时间 t_i"); E --> F("累加总等待时间: total_wait = total_wait + current_wait"); F --> G("更新当前等待时间: current_wait = current_wait + t_i"); E -- 循环结束 --> H("计算平均等待时间 = total_wait / n"); H --> I("结束"); ``` --- ### 2. 运行效果图及测试数据 #### 2.1 背包问题 ![](../assets/Lab03-backpack.png) 结论是: 当所有物品的单位价值（value/weight）相同时, 贪心算法能求得0-1背包问题的最优解 #### 2.2 最短等待时间问题 ![](../assets/Lab03-shortest-wait-time.png) 对于最短等待时间问题, 贪心算法总能得到最优解 --- ### 3. 心得体会 通过本次实验，我对贪心算法的本质、适用场景和局限性有了更为深刻和具象化的理解。 **1.遇到的问题及解决方法** * **问题一：如何有效证明贪心在0-1背包问题上是“错”的？** * **遇到的问题**：仅凭一个例子说明贪心算法得不到最优解，似乎缺乏说服力。如何能确定真正的最优解是多少，从而进行有力的对比？ * **解决方法**：我意识到需要一个“参照物”。因此，我额外学习并实现了动态规划算法来求解0-1背包问题。因为动态规划能够保证得到最优解，所以它可以作为衡量贪心算法结果的“黄金标准”，使得对比分析非常清晰、有力。 * **问题二：如何证明调度问题的贪心策略是“对”的？** * **遇到的问题**：“最短时间优先”这个策略非常直观，但直觉不等于证明。如何从逻辑上严格证明它的正确性？ * **解决方法**：我查阅了相关资料，学习了“邻项交换法”（Argument by Exchange）。通过假设存在一个非按最短时间排序的最优解，并证明通过交换其中一对“错误”顺序的相邻项总能使结果变得更好，从而产生矛盾，反证了原策略的正确性。这个过程锻炼了我的逻辑思维和数学证明能力。 **2.实验过程中的收获** * **深刻理解了贪心算法的本质**：贪心算法的精髓在于“局部最优”，它在每一步都做出当下看起来最好的选择，并期望通过一系列局部最优得到全局最优。本次实验清晰地揭示了：对于某些问题（如背包问题、最短平均等待时间），这种策略是有效的；而对于另一些问题（如0-1背包问题），局部最优并不能导向全局最优。 * **掌握了判断贪心算法适用性的关键**：一个问题是否适用贪心算法，取决于它是否满足**贪心选择性质**和**最优子结构**。背包问题（可分割）满足这些性质，因为每次选择性价比最高的物品的一部分来填满剩余空间，这个选择不会影响后续决策，且总是正确的。而0-1背包问题则不满足贪心选择性质，因为当前的选择可能会“占用”掉一些容量，从而使得后续无法做出一个价值更高但组合方式不同的选择。 * **提升了算法设计和验证能力**：本次实验让我学会了不仅仅是实现一个算法，更要去设计实验来验证它、分析它。通过引入动态规划作为对比，以及运用数学方法证明算法的正确性，我的问题分析和解决能力得到了很好的锻炼。 总而言之，本次实验是一次非常成功的理论与实践的结合。它让我真正“看”到了算法的效率差异和适用边界，将书本上抽象的概念转化为了代码运行结果和严谨的逻辑分析，收获颇丰。 ### 4. 附录 #### 4.1 背包问题 ```python def fractional_knapsack_greedy(items, capacity): """ 使用贪心算法解决部分背包问题。 物品按单位价值从高到低排序。 """ # 计算每个物品的单位价值 for item in items: item['density'] = item['value'] / item['weight'] # 按单位价值降序排序 items.sort(key=lambda x: x['density'], reverse=True) total_value = 0 knapsack = [] for item in items: if capacity == 0: break if item['weight'] <= capacity: # 可以完整放入 capacity -= item['weight'] total_value += item['value'] knapsack.append({'name': item['name'], 'weight': item['weight'], 'value': item['value']}) else: # 只能放入一部分 fraction = capacity / item['weight'] total_value += item['value'] * fraction knapsack.append({'name': item['name'], 'weight': capacity, 'value': item['value'] * fraction}) capacity = 0 return total_value, knapsack def zero_one_knapsack_greedy(items, capacity): """ 尝试使用贪心算法解决0-1背包问题。 """ # 计算每个物品的单位价值 for item in items: item['density'] = item['value'] / item['weight'] # 按单位价值降序排序 items.sort(key=lambda x: x['density'], reverse=True) total_value = 0 knapsack = [] for item in items: if capacity >= item['weight']: capacity -= item['weight'] total_value += item['value'] knapsack.append(item) return total_value, knapsack def zero_one_knapsack_dp(items, capacity): """ 使用动态规划解决0-1背包问题。 """ n = len(items) dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] for i in range(1, n + 1): weight = items[i-1]['weight'] value = items[i-1]['value'] for w in range(1, capacity + 1): if weight > w: dp[i][w] = dp[i-1][w] else: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight] + value) return dp[n][capacity] def run_test(test_name, items, capacity): """运行并打印一组测试数据的结果。""" print(f"--- {test_name} ---") print(f"物品: {items}") print(f"背包容量: {capacity}\n") # 贪心算法解决背包问题 fk_value, fk_knapsack = fractional_knapsack_greedy([item.copy() for item in items], capacity) print(f"部分背包问题 (贪心解):") print(f" 总价值 = {fk_value:.2f}") # print(f" 包内物品: {fk_knapsack}\n") # 贪心算法尝试解决0-1背包问题 g_value, g_knapsack = zero_one_knapsack_greedy([item.copy() for item in items], capacity) print(f"0-1 背包问题 (贪心解):") print(f" 总价值 = {g_value}") # print(f" 包内物品: {[item['name'] for item in g_knapsack]}\n") # 动态规划解决0-1背包问题 dp_value = zero_one_knapsack_dp([item.copy() for item in items], capacity) print(f"0-1 背包问题 (动态规划解):") print(f" 总价值 = {dp_value}\n") print("-" * (len(test_name) + 8)) print() # --- 测试数据 --- items1 = [ {'name': 'A', 'weight': 10, 'value': 60}, {'name': 'B', 'weight': 20, 'value': 100}, {'name': 'C', 'weight': 30, 'value': 120}, ] capacity1 = 50 run_test("测试数据 1", items1, capacity1) items2 = [ {'name': 'A', 'weight': 20, 'value': 60}, {'name': 'B', 'weight': 10, 'value': 100}, {'name': 'C', 'weight': 30, 'value': 120}, ] capacity2 = 50 run_test("测试数据 2", items2, capacity2) items3 = [ {'name': 'A', 'weight': 12, 'value': 4}, {'name': 'B', 'weight': 2, 'value': 2}, {'name': 'C', 'weight': 1, 'value': 2}, {'name': 'D', 'weight': 1, 'value': 1}, {'name': 'E', 'weight': 4, 'value': 10}, ] capacity3 = 15 # run_test("测试数据 3", items3, capacity3) items4 = [ {'name': 'A', 'weight': 20, 'value': 100}, {'name': 'B', 'weight': 30, 'value': 120}, ] capacity4 = 50 # run_test("测试样例 4", items4, capacity4) items5 = [ {'name': 'A', 'weight': 10, 'value': 50}, {'name': 'B', 'weight': 20, 'value': 100}, {'name': 'C', 'weight': 35, 'value': 140}, {'name': 'D', 'weight': 15, 'value': 60} ] capacity5 = 30 run_test("测试样例 5", items5, capacity5) ``` #### 4.2 最短平均等待时间问题 ```python def shortest_average_wait_time_solver(customers): """ 使用贪心策略解决最短平均等待时间问题。 """ # 核心贪心策略：按服务时间从小到大排序 # items()返回(key, value)对，x[1]表示按服务时间排序 sorted_customers = sorted(customers.items(), key=lambda x: x[1]) optimal_order = [customer[0] for customer in sorted_customers] total_wait_time = 0 current_wait_time = 0 # 记录当前顾客的等待时间 # 计算总等待时间 # 第一个顾客等待时间为0 # 第二个顾客等待时间为第一个的服务时间 # 第三个顾客等待时间为前两个的服务时间之和，依此类推 for i in range(len(sorted_customers) - 1): current_wait_time += sorted_customers[i][1] # 完成当前顾客服务后，累加到下一个顾客的等待时间上 total_wait_time += current_wait_time n = len(customers) average_wait_time = total_wait_time / n if n > 0 else 0 return optimal_order, total_wait_time, average_wait_time if __name__ == "__main__": customers_data = { '顾客A': 10, # 需要10分钟服务 '顾客B': 3, '顾客C': 5, '顾客D': 8 } print(f"测试数据: {len(customers_data)}个顾客及其所需服务时间 -> {customers_data}") order, total_wait, avg_wait = shortest_average_wait_time_solver(customers_data) print(f"\n结论: 最优服务次序为 -> {order}") print(f"总等待时间: {total_wait} 分钟") print(f"最小平均等待时间: {avg_wait:.2f} 分钟") ```