KnapsackSolve

KnapsackSolve[{cost1,cost2,…},maxtotalcost]

総費用が maxtotalcostを超えてはならないという制約条件のもとで，各 costiに関連付けられた品物の最大数を求めるナップサック問題を解く．

KnapsackSolve[{{payoff1,cost1},{payoff2,cost2},…},maxtotalcost]

総費用に関する制約条件を満足し総利益を最大にする品物数を求める．

KnapsackSolve[{{payoff1,cost1,maxcount1},…},maxtotalcost]

品物 i の個数が最大で maxcountiになることを許す．

KnapsackSolve[items,{maxtotalpayoff,maxtotalcost}]

総利益が maxtotalpayoff を超えない結果を求める．

KnapsackSolve[items,{maxtotalpayoff,maxtotalcost,maxtotalcount}]

合計個数が maxtotalcount を超えないという制約条件を加える．

KnapsackSolve[label1itemspec1,…,maxtotals]

各タイプの品物にラベルをつけ，結果を連想で与える．

詳細

  • KnapsackSolveは，maxtotals で指定された制約条件に従って総利益額を最大にする非負の整数による個数 ci≤maxcountiのリスト{c1,c2,…}を求める．
  • 利益額と費用はすべて，非負の実数かQuantityオブジェクトでなければならない．個数は非負の整数かInfinityでなければならない．
  • 制約条件 maxtotals の可能な指定には，maxtotalcost，{maxtotalcost}，{maxtotalpayoff,maxtotalcost}，{maxtotalpayoff,maxtotalcost,maxtotalcount}がある．
  • デフォルトで，payoffiは1であるとみなされる．最大制約はInfinityであるとみなされる．
  • KnapsackSolveは，maxcountiが省略されるもしくはInfinityである場合は非有界のナップサック問題を，非負の整数の場合は有界ナップサック問題を，すべて1の場合は0-1ナップサック問題を解く．
  • {payoffi,costi,maxcounti}の各集合は<|"Payoff"->payoffi,"Cost"->costi,"MaxCount"->maxcounti|>として与えることもできる．"Payoff"と"MaxCount"は任意とする．
  • 制約条件のパラメータ{maxtotalpayoff,maxtotalcost,maxtotalcount}は<|"MaxTotalPayoff"->maxtotalpayoff,"MaxTotalCost"->maxtotalcost,"MaxTotalCount"->maxtotalcount|>として与えることもできる．"MaxTotalPayoff"と"MaxTotalCount"は任意とする

例題

すべて開くすべて閉じる

例  (4)

c1+c2+c3の合計を最大にしてを満足する品物 ciの数を求める：

を満足し，利益総額3c1+2c2を最大にする，品物 c1と c2の最大数を求める：

利益額，費用，最大数が2セットのナップサック問題を解く：

利益総額と合計数についての追加的な制約がある問題を解く：

連想を使って品物の集合にラベルを付ける：

スコープ  (13)

利益，費用，個別費用  (6)

費用だけを指定してナップサック問題を解く：

省略された利益額は，デフォルトで1に設定される：

利益額と費用の値を指定してナップサック問題を解く：

0-1ナップサック問題は，個々の品物の最大数をすべて1に設定することで得られる：

利益額，費用，個々の品物の最大数を指定する：

キーと値のペアは任意の順序で与えることができる：

規則のリストの代りにAssociationを使う：

品物の集合を指定する：

規則のリストの代りに Associationを使う：

品物の集合と，利益額，費用，個々の品物の最大数の両方を指定する：

合計についての制約  (4)

費用合計について制約があるナップサック問題を解く：

総利益額と費用合計についての制約を指定する：

総利益額，費用合計，総品物数について制約を課す：

制約を指定する：

キーと値のペアは任意の順序で与えることができる：

規則のリストの代りにAssociationを使う：

数量と数量配列  (2)

Quantityオブジェクトを使って利益額あるいは費用を指定する：

互換単位は自動的に変換される：

QuantityArrayオブジェクトを含むナップサック問題を解く：

データ集合  (1)

Datasetオブジェクトを使って項目の集合を指定する：

アプリケーション  (1)

決まった予算内で食品リスト中の果物のカロリーを最大にする：

次は，各果物のカロリーとカロリーの合計である：

次は，各果物の値段と値段の合計である：

特性と関係  (5)

KnapsackSolveはLinearProgrammingの形式に等しい：

利益総額と費用総額は，指定されていなければInfinityに設定される：

maxtotalpayoff をInfinityに設定すると，解に可能な最大合計が返される：

費用と利益は非負の実数でよいが，個数は正の整数でなければならない：

KnapsackSolveは制約条件を満足する解を1つだけ返す：

しかし，それ以外の解が存在することもある：

Wolfram Research (2016), KnapsackSolve, Wolfram言語関数， https://reference.wolfram.com/language/ref/KnapsackSolve.html.

テキスト

Wolfram Research (2016), KnapsackSolve, Wolfram言語関数， https://reference.wolfram.com/language/ref/KnapsackSolve.html.

CMS

Wolfram Language. 2016. "KnapsackSolve." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/KnapsackSolve.html.

APA

Wolfram Language. (2016). KnapsackSolve. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/KnapsackSolve.html

BibTeX

@misc{reference.wolfram_2024_knapsacksolve, author="Wolfram Research", title="{KnapsackSolve}", year="2016", howpublished="\url{https://reference.wolfram.com/language/ref/KnapsackSolve.html}", note=[Accessed: 22-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_knapsacksolve, organization={Wolfram Research}, title={KnapsackSolve}, year={2016}, url={https://reference.wolfram.com/language/ref/KnapsackSolve.html}, note=[Accessed: 22-November-2024 ]}