平衡需求和约束：导航背包问题
#python #problemsolving #machinelearning #msexcel

简介：
想象一下，您正在打包假期，并且必须打包，但是您对航空公司允许您携带的袋子有限制。目标应该是最有价值的物品。我们的焦点：背包问题，选择和能力的难题

问题定义：
为了最大程度地提高您可以包装的物品的总价值，考虑到以下表格，其中包含项目列表，其个人重量和价值。

项目 a b c d e
重量 12 2 1 1 4
value 4 2 2 1 10

您的挑战是战略性地选择列表中的项目组合，以最大化总价值，同时保持严格的重量限制。您的背包只能容纳15个单位的总重量。

方法1：Excel求解器

设置：

  • 决策变量是包装的项目。它是二进制变量（在黄色细胞中突出显示）

  • 目标函数是最大化可以携带的总重量（项目所选权重的总和）。

Image description

Image description

解决方案 ：

项目 b c d e
重量 2 1 1 4
value 2 2 1 10

方法2：Python代码 

import pulp
# Create the problem
prob = pulp.LpProblem("KnapsackProblem", pulp.LpMaximize)
# Data
items = [
    {"name": "A", "weight": 12, "value": 4},
    {"name": "B", "weight": 2, "value": 2},
    {"name": "C", "weight": 1, "value": 2},
    {"name": "D", "weight": 1, "value": 1},
    {"name": "E", "weight": 4, "value": 10}
]
# Decision variables
pick = {item["name"]: pulp.LpVariable(item["name"], cat='Binary') for item in items}
# Objective function: maximize total value
prob += pulp.lpSum([pick[item["name"]] * item["value"] for item in items])
# Constraint: total weight should be less than or equal to 15
prob += pulp.lpSum([pick[item["name"]] * item["weight"] for item in items]) <= 15
# Solve the problem
prob.solve()
# Print the results
print("Status:", pulp.LpStatus[prob.status])
print("Total Value:", pulp.value(prob.objective))
print("Picked Items:")
for item in items:
    if pick[item["name"]].value() == 1:
        print(f"{item['name']} - Weight: {item['weight']}, Value: {item['value']}")

解决方案 ：
Status: Optimal
Total Value: 15.0
Picked Items:
B - Weight: 2, Value: 2
C - Weight: 1, Value: 2
D - Weight: 1, Value: 1
E - Weight: 4, Value: 10

在需求和局限性之间导致微妙的平衡是解决问题和现实生活中的重要技能。保持好奇，继续优化，并记住，在平衡的精致艺术中经常发现估价最大化的途径

进一步读取：

  1. KNAPSACK Problem
  2. Packing problem