序文
アルゴリズムを学ぶ学生にとって、動的プログラミングは彼らが学ばなければならない最も重要な問題の1つです。0-1ナップザック問題は最も古典的な動的プログラミング問題です。このブログも主に動的プログラミングを使用して0-1ナップザック問題を解決します。 。
問題の説明
バックパックの重量とそれに対応する質量は次のとおりです。バックパックの最大耐荷重重量は6kgですが、バックパックの最大耐荷重範囲内のアイテムの質量を最大化するには、どのように取り付けますか？
| アイテム番号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 重量 | 3kg | 1kg | 2kg | 4kg |
| 品質 | 6円 | 10円 | 5円 | 10円 |
問題分析のための動的プログラミング
まず、dp [i] [j]の配列を作成します。bag[index]配列は、アイテムの重量と品質を表します。
( bag [index] [0]は重量、bag [index] [1]は質量、iはアイテム、jは現在のバックパックが耐えられる最大重量、dp [i] [j]は現在の重量を意味します。バックパックの重量がjのときに保持できる最大質量。この時点で、動的転送方程式を待つことができます。
| dp[i][j] = max(dp[i-1][j], dp[i-1][j-bag[index][0]]+bag[index][1]) |
|---|
方程式の分析;アイテムをトラバースする場合、ロードと非ロードの2つの状況に分けられます。
アイテムをロードしないでください。dp[i] [j]の質量は前のアイテムの質量であり、dp [i-1] [j]に等しくなります。iはアイテムを表し、i-1の質量です。
アイテムをロードします。dp[i-1] [j-bag [index] [0]] + bag [index] [1]、iは現在のi番目のアイテムを表し、i-1は前のアイテムを表します。現在のバックパックが運ぶことができる最大質量を示します。したがって、j-bag [index] [0]は、アイテムをロードする場合、アイテム（つまり、i-1番目のアイテム）を受け取る必要があるバックパックの最大容量がj-であることを意味します。 bag [index] [0]、i番目のアイテムは容量jのバックパックで満たされているためです。
コード解決
| bag、n、dp = [[6,3]、[10,1]、[5,2]、[10,4]]、6、[]＃bagはアイテムの重量とそれに対応する質量を表し、nはi in range（len（bag））の場合：dp.append（[0] *（n + 1））for i in range（n + 1）：if i> = bag [0] [1]： dp [0] [i] = bag [0] [0]＃最初のアイテムに対応する最大質量は、範囲（1、len（bag））内のiについて初めて配列をトラバースすることによって取得されます：for j in range（n + 1）：if bag [i] [1] <= j：dp [i] [j] = max（dp [i-1] [j]、dp [i-1] [j-bag [ i] [1]] + bag [i] [0]）＃dp [i] [j]の現在の最大質量を取得print（dp [-1] [-1]）＃最終的なdp j = n（最大のバックパック）を印刷します容量）最高品質 |
|---|
総括する
このブログでは、主に動的プログラミングを使用して0-1ナップザック問題を解決する方法について説明します。一般に、0-1ナップザック問題は古典的な動的プログラミング問題であり、dp配列を使用して必要な値を記憶し、関連する次の値を導き出します。値。
Recommended Posts