【QAP.練習問題1】:0-1ナップサック問題【量子コンピュータ/アニーリング@Python/Fixstars Amplify】
【はじめに】
第(1-2,5-6)回でざっと「Fixstars Amplify」の基本的な使い方をまとめた。
その内容を踏まえてもう「0-1ナップサック問題」を解いてみる。
【練習問題1】
6個のアイテム:(x_0, x_1, x_2, x_3, x_4, x_5)があり、それぞれ「商品価値」と「重さ」が設定されている。
これらのアイテムを「ナップサック(リュック)」に詰めて運びたいが、ナップザックにも「耐久重量」がある。
6つのアイテムに対する「商品価値」・「重さ」と「ナップザックの耐久重量」の設定値は次のとおりである。
![](https://assets.st-note.com/img/1644677239094-s0g4HzYlIg.png?width=1200)
「ナップサックの耐久重量」の範囲で、6つのアイテムから適当に選びつつ、「詰め込んだアイテムの商品価値の総和」をできるだけ大きくしたい。
どのような組み合わせで選ぶとよいだろうか?
【解答例】
実行環境は「Fixstars Amplify」+「Google Colab」でやる。
【1】ライブラリのインストール
! pip install amplify
! pip install --upgrade amplify
【2】クライアントオブジェクトの作成
from amplify.client import FixstarsClient
client = FixstarsClient()
client.parameters.timeout = 1000 # タイムアウトは1000ミリ秒(1秒)
client.parameters.outputs.duplicate = True # みつかった解が複数あってもOK
client.parameters.outputs.num_outputs = 0 # 0: 見つかった解を全て出力
# トークン設定
client.token = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" # 無料登録して取得したトークンを指定する
※トークンは掲載上「XXX... ...XXX」としているが、実際は「Fixstars Amplify」に無料登録して取得したトークンを設定する。
【3】サンプルデータを用意する
今回は
・商品価値:p
・重量:w
・ナップザックの耐久重量:c
とおく。
# サンプルデータ
p = [10, 13, 18, 31, 7, 15] # 価値
w = [11, 15, 20, 35, 10, 33] # 重さ
c = 47 # 耐久重量
I = range(len(w))
【4】QUBO/イジング変数を用意する
今回の場合は「6つのアイテム」にそれぞれ対し、
リュックに入れない/入れるのフラグを「0 or 1」で表す
■フラグのイメージ図
![](https://assets.st-note.com/img/1644679173158-dmZFsNa81u.png?width=1200)
これを踏まえて、「0 or 1」のいずれかをとる「QUBO変数」を6つ用意する。
from amplify import BinaryPoly, SymbolGenerator
gen = SymbolGenerator(BinaryPoly) # BinaryPoly の変数ジェネレータを宣言
q = gen.array(len(w))
q
【ここまでの実行結果】
[q_0, q_1, q_2, q_3, q_4, q_5]
【5】目的関数
今回の「目的関数」は「価値の合計値」を「できるだけ大きく」する
ここから先は
¥ 100
もっと応援したいなと思っていただけた場合、よろしければサポートをおねがいします。いただいたサポートは活動費に使わせていただきます。