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

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

ナップサック問題

重さが $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事典」の他の用語

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

索引トップ用語の索引ランキング

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.