翻訳と辞書
Words near each other
・ ナッパ (曖昧さ回避)
・ ナッピィモール
・ ナッピー・ブラウン
・ ナッフィールド・オックスフォード タクシー
・ ナッフィールド・オーガニゼーション
・ ナップ
・ ナップ (トランプ)
・ ナップサック
・ ナップサック問題
・ ナップザック
ナップザック問題
・ ナップザック暗号
・ ナップス
・ ナップス (神奈川県)
・ ナップスター
・ ナップスタージャパン
・ ナップルテール
・ ナップ・ラジョイ
・ ナッポスユナイテッド
・ ナッレス


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

ナップザック問題 : ミニ英和和英辞書
ナップザック問題[だい]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [もん]
 【名詞】 1. problem 2. question 
問題 : [もんだい]
 【名詞】 1. problem 2. question 
: [だい]
  1. (n,vs) title 2. subject 3. theme 4. topic 

ナップザック問題 ( リダイレクト:ナップサック問題 ) : ウィキペディア日本語版
ナップサック問題[なっぷさっくもんだい]

ナップサック問題(ナップサックもんだい、Knapsack problem)は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 ''C'' のナップサックが一つと、''n'' 種類の品物(各々、価値 ''p''''i'', 容積 ''c''''i'')が与えられたとき、ナップサックの容量 ''C'' を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合(''x''''i'' ∈ )や、同じ品物をいくつでも入れてよい場合(''x''''i'' ∈ 0以上の整数)など、いくつかのバリエーションが存在する。
決定問題としてのナップサック問題は、「''C'', ''p''''i'', ''c''''i'' のほかに価値の合計の目標 ''V'' が与えられたとき、容量 ''C'' 以内でナップサック内の品物の価値の合計が ''V'' 以上になるような品物の選び方はあるか」を判定することである。
全ての品物について ''p''''i'' = ''c''''i'' が成り立つとき、部分和問題と等価であるため、ナップサック問題は部分和問題を一般化したものといえる。ナップサック問題は、(部分和問題もそうだが)NP困難と呼ばれる問題のクラスに属する。なお、部分和問題は同時にNP完全(NPかつNP困難)と呼ばれるクラスにも属する。
動的計画法を用いた擬多項式時間アルゴリズムFPTAS の存在が知られているため、実用的には、ほぼ最適解を得られる。
== 0-1 ナップサック問題 ==
各種類の品物はそれぞれ1つずつしかない場合を 0-1 ナップサック問題 という。動的計画法で厳密解が求まる。
問題文は数式では以下のように表現される。
: \sum_^n c_i x_i \le C, \quad x_i \in \ の元で \sum_^n p_i x_i の最大値を求める
mj を i 番目までの品物を使い、容量 j での最大値とする。mC が求める答え。
mC = 下記2つの大きい方
xn = 0 の場合:つまり品物 n を積まないか、もしくは、品物 n の cn が大きすぎて積めない場合
m- 1, C
xn = 1 の場合:つまり品物 n を積む場合
m- 1, C - cn + pn
これをボトムアップの動的計画法にした擬似コードは以下の通り。

for (j from 0 to C)
for (i from 1 to n)

Groovy でトップダウンの動的計画法(メモ化再帰)を使ったコードは以下の通り。

@Memoized int m(int i, int j)


抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「ナップサック問題」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Knapsack problem 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.