knapsack problemとは何？わかりやすく解説 Weblio辞書

すべての辞書から再検索する

OR事典

索引トップランキングカテゴリー

ナップサック問題

重さが $a_i\,$ の物品 $i\,$ をナップサックに詰めるとき, 重量制限 $b\,$ の下で価値 $c_i\,$ の総和が最大になるものを選ぶという次の整数計画問題.

目的関数	$\sum_{i=1}^{n} c_{i}x_{i} \to \,$ 最大化
制約条件	$\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,$ ：非負整数

ナップサック問題ともいう. 重さが $a_i\,$ の物品 $i\,$ をナップサックに詰めるとき, 重量制限 $b\,$ の下で価値 $c_i\,$ の総和が最大になるものを選ぶという次の整数計画問題.

目的関数	$\sum_{i=1}^{n} c_{i}x_{i} \to \,$ 最大化
制約条件	$\sum_{i=1}^{n} a_{i}x_{i} \leq b,x_i\,$ ：非負整数

「OR事典」の他の用語

グラフ･ネットワーク：	ダイクストラ法ダルメジ・メンデルゾーン分解デルタマトロイドナップサック問題ネットワークネットワークフロー問題フェンシェル型双対定理
組合せ最適化：	グラフ彩色問題グレブナー基底データ構造ナップサック問題ネットワークフロー問題ハッシュ表パーフェクトグラフ
近似・知能・感覚的手法：	タブー探索デンプスター・シェファーの証拠理論データマイニングナップサック問題ニューラルネットワークニューラルネットワークによる学習ファジィランダム変数