时间戳

首页 > 解决方案 > 有没有办法在纸浆中检索下一个最佳最佳解决方案？

python - 有没有办法在纸浆中检索下一个最佳最佳解决方案？

问题描述

下面列出了一个非常简单的背包问题。

df 的示例如下所示：

| weight | item  | profit |
|--------|-------|--------|
| 1      | item1 | 3.977  |
| 2      | item2 | 3.126  |
| 3      | item3 | 2.698  |
| 4      | item4 | 2.607  |
| 5      | item5 | 2.569  |

目标是在选择组合权重 >=10 的四个项目时最大化利润。我要解决的代码如下：

prob = LpProblem("Weight",LpMaximize)
player_vars = [pulp.LpVariable(f'Item_{row.item}', cat='Binary') for row in df.itertuples()]

# total items  constraint
prob += pulp.lpSum(player_var for player_var in player_vars) == 4

# total weight constraint
prob += pulp.lpSum(df.Seed.iloc[i] * player_vars[i] for i in range(len(df))) >= 10

# problem
prob += pulp.lpSum([df.profit.iloc[i] * player_vars[i] for i in range(len(df))])

# solve and print the status
prob.solve()
print(LpStatus[prob.status])
    
#print results
    for i in range(len(df)):
        if player_vars[i].value() == 1:
            row = df.iloc[i]
            print(row.item, row.weight,row.profit)

我想知道是否有办法使用纸浆获得第二好的答案等等？谢谢！

标签： pythonoptimizationpulp

解决方案

一种方法是通过添加一个额外的约束来重新解决问题，以禁止现有的最佳解决方案。例如说原始问题的解决方案存储为player_vars_soln，然后您将添加一个约束：

prob += pulp.lpSum(player_vars_soln[i]*player_vars[i] for i in range(len(df))) <= 3

推荐阅读