个人主页:丷从心
系列专栏:回溯法
{ max ? ∑ i = 1 n w i x i s . t . ∑ i = 1 n w i x i ≤ c 1 x i ∈ { ? 0 , 1 ? } , 1 ≤ i ≤ n \begin{cases} \max{\displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}}} \\ s.t. \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c_{1} \end{cases} \kern{2em} x_{i} \in \set{0 , 1} , 1 \leq i \leq n ? ? ??maxi=1∑n?wi?xi?s.t.i=1∑n?wi?xi?≤c1??xi?∈{0,1},1≤i≤n
Python
实现def backtrack_loading(weights, capacity):
n = len(weights)
best_solution = []
best_value = 0
def constraint(solution):
# 约束函数: 检查当前解是否满足容量限制
total_weight = sum(item for item in solution)
return total_weight <= capacity
def bound(solution, index):
# 限界函数: 计算当前解的重量总和加上剩余物品重量作为上界, 用于剪枝
total_weight = sum(item for item in solution) + sum(weight for weight in weights[index + 1:])
return total_weight
def backtrack(solution, value, index):
nonlocal best_solution, best_value
if index == n:
# 已经遍历完所有物品
if value > best_value:
# 如果当前解的重量更大, 更新最优解
best_solution = solution
best_value = value
return
# 尝试选择当前物品
weight = weights[index]
if constraint(solution + [weight]) and bound(solution + [weight], index) >= best_value:
# 如果满足约束函数, 继续探索下一个物品
backtrack(solution + [weight], value + weight, index + 1)
# 尝试不选择当前物品
if bound(solution, index) >= best_value:
# 如果当前解的上界仍然可能更好, 继续探索下一个物品
backtrack(solution, value, index + 1)
# 开始回溯搜索
backtrack([], 0, 0)
return best_solution, best_value
weights = [2, 4, 5, 7]
capacity = 10
best_solution, best_value = backtrack_loading(weights, capacity)
print(f'最优解: {best_solution}')
print(f'最优值: {best_value}')
最优解: [2, 7]
最优值: 9