玩具示例¶

类别： 装箱

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

我们描述背包问题的一个玩具示例。我们考虑 8 件物品，其重量分别为 10、60、30、40、30、20、20、2，价值分别为 1、10、15、40、60、90、100、15。目标是确定一个物品子集，使其总重量不超过 102，并且总价值尽可能大。

学习要点¶

使用 OptAgent 区分决策变量与由决策推导出的中间表达式
使用布尔决策变量表示物品是否被选中

建模思路¶

对每件物品定义一个布尔决策变量，若该物品被选中则为真。所选物品的总重量和总价值均为由决策变量推导出的中间表达式，而不是额外的决策变量。模型约束总重量不超过 102，并最大化总价值。

Python 实现¶

from optagent import OptModel, solve


def main(time_limit=10):
    weights = [10, 60, 30, 40, 30, 20, 20, 2]
    values = [1, 10, 15, 40, 60, 90, 100, 15]
    knapsack_bound = 102

    model = OptModel()

    # x[item] is true when the item is selected.
    x = [model.bool() for item in range(len(weights))]

    knapsack_weight = model.sum(weights[item] * x[item] for item in range(len(weights)))
    model.constraint(knapsack_weight <= knapsack_bound)

    knapsack_value = model.sum(values[item] * x[item] for item in range(len(values)))
    model.maximize(knapsack_value)

    solution = solve(model, time_limit_s=float(time_limit))
    if not solution.feasible:
        print(f"No feasible selection found; Status = {solution.status}")
        return solution

    selected_items = [item for item, selected in enumerate(x) if selected.value]
    print(
        f"Selected items = {selected_items}; Weight = {knapsack_weight.value}; "
        f"Value = {knapsack_value.value}; Status = {solution.status}"
    )
    return solution

solution = main(time_limit=1)