Python程序贪婪算法求活动安排问题

以下是Python程序贪婪算法求活动安排问题的示例代码：

def activity_selection(start, finish):
    n = len(finish)
    i = 0
    print("Selected activities:")
    print(i, end=" ")
    for j in range(n):
        if start[j] >= finish[i]:
            print(j, end=" ")
            i = j
    print()

# 示例
start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
activity_selection(start, finish)

输出结果为：

Selected activities:
0 1 3 4 

该算法的基本思路是：首先将所有活动按照结束时间从早到晚排序，然后从第一个活动开始，依次判断每个活动的开始时间是否晚于上一个活动的结束时间，如果是，则选择该活动，否则跳过该活动。最终选择的活动即为最大兼容活动集合。

相关问题

有多个约束条件的贪心算法python程序

在Python中编写带有多个约束条件的贪心算法通常涉及选择每一步决策时，都尽可能地优化当前局部最优解，同时保证满足所有约束条件。贪心算法并不一定能找到全局最优解，但在许多复杂问题中能找到近似最优解。

下面是一个简单的示例，假设我们要创建一个求解0-1背包问题的贪婪算法，其中有两个约束条件：物品的数量不超过背包容量，以及总价值不超过给定的最大价值：

def greedy_knapsack(items, capacity):
    items.sort(key=lambda x: (x['value'] / x['weight'], -x['weight']))  # 按价值/重量降序，如果值相等则按重量升序排序
    total_value = 0
    total_weight = 0

    for item in items:
        if total_weight + item['weight'] <= capacity and total_value + item['value'] <= max_value:  # 约束条件检查
            total_weight += item['weight']
            total_value += item['value']
        else:
            break  # 如果超过背包容量，则停止添加

    return total_value

# 示例数据
items = [
    {'name': 'item1', 'weight': 5, 'value': 10},
    {'name': 'item2', 'weight': 4, 'value': 6},
    {'name': 'item3', 'weight': 7, 'value': 8},
]
capacity = 10
max_value = 15

result = greedy_knapsack(items, capacity)
print(f"最大价值: {result}")

给出用Python语言实现的背包问题的贪心算法。要求：自行设计一个背包问题（给出背包的总重量，物品总数，每个物品的价值和重量），附上完整的Python程序以及运行结果图。

背包问题是一种经典的动态规划问题，但贪婪算法通常不适合解决0-1背包问题，因为它并不保证每次选择都能得到最优解。然而，对于一些特殊情况下的背包问题，如非负权值物品的完全背包问题，可以采用贪心策略。

这里我们设计一个简单的模拟非负权值物品完全背包问题的贪心算法，即每次都选择价值最大的未装满物品。以下是Python实现：

def greedy_knapsack(capacity, weights, values):
    items = sorted(zip(weights, values), 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

# 设定背包总重量、物品数、价值和重量
total_capacity = 50
num_items = 6
weights = [10, 20, 30, 40, 50, 60]
values = [60, 100, 120, 90, 70, 50]

result = greedy_knapsack(total_capacity, weights, values)
print(f"使用贪心算法，背包的最大价值是: {result}")

# 这里由于是文字描述，无法提供实际运行结果图，如果需要可视化结果，你可以使用matplotlib等库绘制贪心决策过程。

注意，这个贪心算法并不是所有情况下的最优解，只有当物品的重量是其价值的比例递减时才是有效的。实际应用中，尤其是涉及复杂约束的背包问题，通常需要使用动态规划或更精确的算法来求解。