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 發布。請參閱許可證文件。