グリーディアルゴリズムを最適化する考えはありますか？

Question

私は最近、Pythonを使ってバックパックの問題を解決するプログラムを書いた。それは素晴らしい作品と、一般的に貪欲アルゴリズム（すなわち、それは最後になるまで、すべてのステップのための最善の解決策を見つける）

に従いますが、私は最適化する必要がそれは貪欲アルゴリズム に基づいて（それは私の宿題の一部です）

それを改善するための基本的なアイデアを教えていただけますか？

Item Name    Weight   Profit 
    Ammunition    3.00   95.00 
    Bread     3.60   90.00 
    Firewood    2.50   56.00 
    Olive Oil    2.40   45.00 
    Water     3.70   67.00 
    Weapon     4.80   79.73 

これは私の現在のプロジェクトの出力です。バッグの容量は20kgに制限されていますが、データを変更することはできませんが、改善のためのより良いアイデアが必要です。ありがとうございました！

私は、コードまたは溶液わからないですが、私はそれがすべての「効率」

Answer 1

ここで私は同意語用語「空間」と「重量」を使用しますに関係していると思います。

あなたができることは、各項目に対してprofit/weightの割合を計算することです。比率の差がいくつかのスペースを掛け合わせることが、そのスペースのための最良の改善である。たとえば、スペースが空いていて、再配置した場合に他のアイテムZを押し込むことができるかもしれない場合、そのスペースから得られる最大の利益は（Zratio-0ratio）*の重量になります。このようにして、欲張りアルゴリズムに基づいて候補ソリューションを生成し、これを使用して改善可能性を制限することができます。一般的には、動的プログラミングの観点からこれにアプローチしたいと思うでしょう。