练习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 = 0best_k = 0for 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_profitbest_k = kf[i][j] = max_profitdecision[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_factoryinvestment_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 = capacityitems_selected = [0] * nfor i in range(n, 0, -1):if dp[i][w] != dp[i-1][w]:items_selected[i-1] = 1w -= weights[i-1]max_value = dp[n][capacity]return max_value, items_selectedvalues = [8, 5, 12]
weights = [3, 2, 5]
capacity = 5max_value, items_selected = knapsack(values, weights, capacity)print(f"最大价值: {max_value}")
print(f"选中的物品: {items_selected}")
#最大价值: 13；选中的物品: [1, 1, 0]
练习3
A地到 E 地要铺设一条煤气管道，其中需经过三级中间站，两点之间的连线上的数字表示距离。如图所示，问应该选择什么路线，使总距离最短？
