0-1 napsack دون تكرار

Question

سؤالي هو السبب في مشكلة O (NW) في مشكلة الحنزات الزائفة متعدد الحدود.

قرأت الكثير من التفسير في Stackoverflow، لكنني لا أفهمها حقا. ( https://stackoverflow.com/questions / 19647658 / ما هو-هو-هو-زخرفة الزمن - كيف لا تختلف من وقت متعدد الحدود ، https://stackoverflow.com/questions/4538581/Why- IS-the-the-napsack-pseudo-pseudo-polynomial # الإجابة -538668 )

الشيء الأساسي هو السبب في أن علينا أن نفكر فقط "W" ك "Logw" بت المدخلات، وليس "n" بطبقات "سجل N".

قال العديد من التفسير أن "W" هو عدد صحيح ولكن "N" هو مجرد عدد البند. لذلك فقط "W" الحجم يتناسب مع "logw".

أعتقد أن هذا المنطق يجب أن يطبق على "n".

على افتراض أننا نسترق العناصر من 1 إلى n، لتمييز العناصر،

علينا حساب الأرقام من 1 إلى n.

أعتقد أنه هو نفسه أن الحلقة تقوم بتكرار ث مرات.

لذلك أعتقد أنه هو نفسه مع "W" لأن هذا العد يحتاج أيضا إلى بت "سجل N".

ماذا أفعل - فهم في هذه المشكلة؟

شكرا.

Answer 1

هنا هو كيف ترميز المدخلات:

• وزن وقيمة البند 1.
• وزن وقيمة البند 2.
• ...
• الوزن وقيمة العنصر $ n $ .
• $ W $ .

يفترض أن الوزن والقيمة أعداد صحيحة، على الأكثر $ M $ ، وكلاهما يتم ترميزه في ثنائي، كما هو $ W $ .ثم طول الترميز هو $$ \ أوميغا (n + \ log w)، o (n \ log m + \ log w). $ نأمل أن يوضح هذا الفرق بين $ n $ و $ W $ .