ホームページ >バックエンド開発 >PHPチュートリアル >PHP動的プログラミングで0-1ナップザック問題を解く 例題分析、0-1例題分析_PHPチュートリアル
PHP動的プログラミングで0-1ナップザック問題を解く 例題分析、0-1例題分析_PHPチュートリアル
- WBOYオリジナル
- 2016-07-13 10:01:021054ブラウズ
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 プログラミング設計に役立つことを願っています。
声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。