PHP動的プログラミングで0-1ナップザック問題を解く 例題分析、0-1例題分析_PHPチュートリアル

PHP動的計画法で0-1ナップサック問題を解く例題分析、0-1事例分析

この記事では、PHP動的計画法を分析して0-1ナップサック問題を解決します。参考のためにみんなで共有してください。具体的な分析は次のとおりです:

ナップサックの問題の説明: 最大重量 W のバックパックには n 個のアイテムがあり、各アイテムの重量は t、各アイテムの値は v です。
このバックパックの重量を最大にする (ただし W を超えない) には、バックパックの値が最大である必要があります。

アイデア: 2 次元配列を定義します。1 つの次元は項目の数 (各項目を表す)、2 番目の次元は重み (最大値を超えない、ここでは 15) です。次の配列 a、
動的計画法の原理的な考え方、max(opt(i-1,w),wi+opt(i-1,w-wi))のうちの最大値
opt(i-1,w-wi) は前の最適解を参照します

この記事で説明した内容が皆様の PHP プログラミング設計に役立つことを願っています。