最大加权独立集问题？

Question

1.创建包含 100 个节点的路径图，并在每个节点上分配 1 到 50 的随机权重。
2.实现动态规划算法的递归版本，以计算刚刚在步骤 1 中创建的图形的最大权重独立集。
3.实现著名而优雅的动态规划版本，其中独立集以自下而上的迭代方式计算。

Answer 1

import random

# Set a fixed random seed for reproducibility
random.seed(42)

# Create a path graph with 100 nodes
# Each node is assigned a random weight between 1 and 50
weights = [random.randint(1, 50) for _ in range(100)]

weights[:10]  # Display the weights of the first 10 nodes

[41, 8, 2, 48, 18, 16, 15, 9, 48, 7]

def mwis_recursive(i, weights, cache):
    # Base case: negative index means an empty set
    if i < 0:
        return 0

    # If the result is in the cache, return it
    if i in cache:
        return cache[i]

    # Recursive case: either include node i and skip node i-1, or skip node i and include node i-1
    include_i = weights[i] + mwis_recursive(i - 2, weights, cache)
    exclude_i = mwis_recursive(i - 1, weights, cache)

    # Save the result in the cache and return it
    cache[i] = max(include_i, exclude_i)
    return cache[i]

# Initialize the cache
cache = {}

# Compute the maximum weight of the independent set
max_weight_recursive = mwis_recursive(len(weights) - 1, weights, cache)

max_weight_recursive

结果：1519

def mwis_iterative(weights):
    # Initialize the array for the maximum weight of the independent set for each subproblem
    max_weights = [0] * (len(weights) + 1)

    # Compute the maximum weight of the independent set for each subproblem
    for i in range(len(weights)):
        include_i = weights[i] + max_weights[i - 1]
        exclude_i = max_weights[i]
        max_weights[i + 1] = max(include_i, exclude_i)

    # Compute which nodes are included in the maximum weight independent set
    included = []
    i = len(weights)
    while i > 0:
        if weights[i - 1] + max_weights[i - 2] > max_weights[i - 1]:
            included.append(i - 1)
            i -= 2
        else:
            i -= 1

    return max_weights[-1], included[::-1]

# Compute the maximum weight of the independent set and which nodes are included
max_weight_iterative, included_nodes = mwis_iterative(weights)

max_weight_iterative, included_nodes

最大权重独立集中的节点为：[0, 3, 5, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 55, 57, 59, 61, 63, 66, 68, 71, 73, 76, 78, 80, 82, 84, 87, 89, 91, 93, 95, 97, 99]