{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 背包问题\n",
    "\n",
    "**类别：** 装箱\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/knapsack-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**背包问题**定义如下。考虑一组具有不同重量和价值的物品。我们需要选择一个物品子集放入一个已知容量的背包中。背包中物品的总重量不得超过其容量。目标是最大化背包中物品的总价值。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 了解 OptAgent 的建模方式：[区分决策变量与中间表达式](https://optagent.pages.dev/guide/modeling/)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "我们提供来自 [OR Library](http://people.brunel.ac.uk/~mastjjb/jeb/info.html) 的实例。数据集的格式如下：\n",
    "\n",
    "- 物品的数量\n",
    "- 对每个物品，其重量\n",
    "- 对每个物品，其价值\n",
    "- 该实例的已知上界\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "我们将背包问题建模为整数规划。对每个物品，我们定义一个 布尔决策变量，当物品被选中时为 1，否则为 0。我们使用 **sum** 算子计算被选中物品的总重量。注意，我们是从决策变量的值推导出这个值：总重量是一个中间表达式，而非决策变量。定义它之后，我们可以约束总重量小于背包的容量。类似地，我们定义另一个中间表达式，对应于被选中物品的总价值。最后，我们最大化该总价值。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_instance(filename):\n",
    "    values = [int(value) for value in Path(filename).read_text(encoding=\"utf-8\").split()]\n",
    "    iterator = iter(values)\n",
    "    nb_items = next(iterator)\n",
    "    weights = [next(iterator) for _ in range(nb_items)]\n",
    "    profits = [next(iterator) for _ in range(nb_items)]\n",
    "    knapsack_capacity = next(iterator)\n",
    "    return nb_items, weights, profits, knapsack_capacity\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=20):\n",
    "    nb_items, weights, profits, knapsack_capacity = read_instance(input_file)\n",
    "    model = OptModel()\n",
    "\n",
    "    # x[i] is true when item i is selected.\n",
    "    selected = [model.bool() for i in range(nb_items)]\n",
    "\n",
    "    # Keep the original Hexaly formulation: weight and value are intermediate expressions.\n",
    "    knapsack_weight = model.sum(\n",
    "        selected[i] * weights[i] for i in range(nb_items)\n",
    "    )\n",
    "    model.constraint(knapsack_weight <= knapsack_capacity)\n",
    "\n",
    "    knapsack_value = model.sum(\n",
    "        selected[i] * profits[i] for i in range(nb_items)\n",
    "    )\n",
    "    model.maximize(knapsack_value)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    selected_items = [\n",
    "        i for i, variable in enumerate(selected) if variable.value\n",
    "    ]\n",
    "    print(\n",
    "        f\"Items = {nb_items}; Capacity = {knapsack_capacity}; \"\n",
    "        f\"Weight = {knapsack_weight.value}; Value = {knapsack_value.value}; \"\n",
    "        f\"Status = {solution.feasible}\"\n",
    "    )\n",
    "    print(\"Selected items:\", selected_items)\n",
    "\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(\n",
    "            f\"{knapsack_value.value}\\n\"\n",
    "            + \" \".join(map(str, selected_items))\n",
    "            + \"\\n\",\n",
    "            encoding=\"utf-8\",\n",
    "        )\n",
    "    return solution\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "以下代码格演示如何调用 OptAgent 背包模型。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_toy = main(INSTANCE_DIR / \"toy.in\", time_limit=1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_100_1 = main(INSTANCE_DIR / \"kp_100_1.in\", time_limit=1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97b9bf38",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.14.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}