十進数を使ったナップザックアルゴリズム？

誰かが私を正しい方向に向けることができますか？私は10進値を使用するナップザックアルゴリズムの変種を探しています。具体的には、質問に答えるために財務値（小数点）を使用します。リストの小数点以下の値のうち、小数点以下の桁数を指定します。十進数を使ったナップザックアルゴリズム？

ご協力いただきありがとうございます。

出典

2016-04-08 psabela

整数のためのすべてのロジックは、小数に適用されます。整数をセントとみなしてください。 – Gene

実際はやや異なっているようです。少なくとも複雑さはかなり異なっているので、小数点以下を整数式に差し込むだけの問題ではありません。 – Carlos

項目値の小数点または決定変数が明確になっていますか？あなたは今両方の答え（遺伝子のコメントです）を持っていますが、それらは根本的に異なり、正しいものを選択する必要があります。 – harold

https://en.wikipedia.org/wiki/Continuous_knapsack_problem

ここで、動的プログラミングの必要はありません、貪欲アルゴリズムが動作します：ちょうど彼らの価値/重量比で項目をソート

出典

2016-04-08 14:45:24 BlackBear

私のアルゴリズムの教科書を見ると、ナップザックの問題は欲張りなナップザックの問題と同じですか？ – psabela

問題とアルゴリズムは2つの異なるものです。しかし、はい、私はその1つに言及している – BlackBear

私は正確な答えを見つける必要があるので - ナップザックは容量に満たされなければならない - 分数は許されない、私は連続/貪欲ナップザックを使用することはできません。欲張りの結果がナップザックを容量に満たさない場合、アルゴリズムは、ナップザックを満たすアイテムの組み合わせを試し続けなければならない。 – psabela

十進数を使ったナップザックアルゴリズム？

答えて

関連する問題