运筹学练习Python精解——动态规划

标签：Python max 50 60 profit range 精解 investment 运筹学

练习1

设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示，试给出收益最大的投资计划。

利润\投资	0	10	20	30	40	50	60
\(g_1(r)\)	0	20	50	65	80	85	85
\(g_2(x)\)	0	20	40	50	55	60	65
\(g_3(x)\)	0	25	60	85	100	110	115
\(g_4(x)\)	0	25	40	50	60	65	70

初始化：初始化一个动态规划表 f 和一个决策表 decision。f 用于存储最大利润，decision 用于记录每个工厂的最佳投资决策。
递归计算：
- 对于每个工厂\(i\)从1到4。
- 对于每个可能的投资金额 \(j\) 从0到60。
- 对于每个可能分配给当前工厂\(i\)的投资金额 \(k\)（以10为步长），使用递归关系计算最大利润，并记录最佳决策。
回溯最优解：
- 从决策表 decision 中回溯，找到每个工厂的最佳投资方案。

import numpy as np

# 表中的利润函数
g = np.array([
    [0, 20, 50, 65, 80, 85, 85],
    [0, 20, 40, 50, 55, 60, 65],
    [0, 25, 60, 85, 100, 110, 115],
    [0, 25, 40, 50, 60, 65, 70]
])

# 工厂数量和总投资
num_factories = 4
total_investment = 60

# 初始化DP表和决策表
f = np.zeros((num_factories + 1, total_investment + 1))
decision = np.zeros((num_factories + 1, total_investment + 1), dtype=int)

# 填充DP表和决策表
for i in range(1, num_factories + 1):
    for j in range(total_investment + 1):
        max_profit = 0
        best_k = 0
        for k in range(0, min(j, 60) + 1, 10):  # 考虑以10为步长的投资
            current_profit = f[i-1][j-k] + g[i-1][k//10]
            if current_profit > max_profit:
                max_profit = current_profit
                best_k = k
        f[i][j] = max_profit
        decision[i][j] = best_k

# 回溯找到最优解
investment_plan = []
remaining_investment = total_investment
for i in range(num_factories, 0, -1):
    invest_in_current_factory = decision[i][remaining_investment]
    investment_plan.append(invest_in_current_factory)
    remaining_investment -= invest_in_current_factory

investment_plan.reverse()  # 反转投资计划，按工厂顺序输出
max_profit = f[num_factories][total_investment]

print(max_profit, investment_plan)
# 160.0 [20, 0, 30, 10]

练习2

求解下面背包问题的最优解。

\[\max \quad z = 8x_1 + 5x_2 + 12x_3 \\ \begin{aligned} s.t.\quad & 3x_1 + 2x_2 + 5x_3 \leq 5 \\ & x_1, x_2, x_3 \geq 0 \quad 整数 \end{aligned} \]

　　

def knapsack(values, weights, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]

    # 回溯找到最优解
    w = capacity
    items_selected = [0] * n
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            items_selected[i-1] = 1
            w -= weights[i-1]

    max_value = dp[n][capacity]
    return max_value, items_selected

values = [8, 5, 12]
weights = [3, 2, 5]
capacity = 5

max_value, items_selected = knapsack(values, weights, capacity)

print(f"最大价值: {max_value}")
print(f"选中的物品: {items_selected}")
#最大价值: 13；选中的物品: [1, 1, 0]

练习3

A地到 E 地要铺设一条煤气管道，其中需经过三级中间站，两点之间的连线上的数字表示距离。如图所示，问应该选择什么路线，使总距离最短？

标签：Python,max,50,60,profit,range,精解,investment,运筹学
From： https://www.cnblogs.com/haohai9309/p/18251392