knapsack

背包

背包问题是一个众所周知的优化问题。例如，在包装集装箱时就会遇到这种情况。运输集装箱具有可容纳的重量。给定要运输的一系列物品，其中每个物品都有一个价值和重量，问题是选择要包装在运输集装箱中的最佳物品。该优化问题可以定义为带有约束的目标：

• 目标：最大化货运价值（所选项目的价值总和）。
• 限制：货物总重量（所选物品的重量总和）必须小于或等于集装箱的容量。

本示例通过将背包问题重新表述为约束二次模型 (CQM) 并将其提交给 Leap 混合 CQM 求解器来解决此类背包问题。

用法

要运行默认演示，请输入命令：

python knapsack.py

要查看可用选项，请输入命令：

python knapsack.py --help

命令行参数允许您选择多个数据集之一（在/data文件夹下）并设置货运能力。数据文件被制定为多行项目，每个项目定义为一对重量和值。

代码概述

knapsack.py中的代码包括三个主要函数：

• build_knapsack_cqm()通过设置目标和约束来创建 CQM，如下所示：

  • 目标：为每个项目创建二元变量，并分配一个等于该项目值的负值的线性偏差。为了最小化这一目标，通过选择一组最佳的物品，相当于最大化货运的总价值。解决方案将选定项目的值设置为 1，将未选定项目的值设置为 0。
  • 约束：使用先前创建的二元变量创建二次模型，其中线性偏差设置为等于每件物品的重量，并要求总重量不得超过容器的容量。

• parse_inputs()是一个实用函数，用于从示例文件中读取数据。

• parse_solution()解析并显示求解器返回的结果。

执照

根据 Apache 许可证 2.0 发布。请参阅许可证文件。