مشكلة تعقيد برمجة البرمجة الديناميكية للقيام $ W= 1 $، هل هي $ o (n) $؟

Question

تعطى مشكلة 0-1 من قبل

$$ \ ادفع {align} & \ text {maximize} \ sum_ {i= 1} ^ n v_ix_i، \ tag {p1} \\ & \ text {somvice to} \ sum_ {i= 1} ^ n w_i x_i \ leq w، \\ & \ text {and} x_i \ in \ {0،1 \}. \ end {align} $

تشغيل خوارزمية البرمجة الديناميكية لهذه المشكلة سيعطي الحل الأمثل في $ O (NW) $ .

إذا قمت بتحديد $ p_i= w_i / w دولار ، أحصل على مشكلة neapsack التالية:

$$ \ ادفع {align} & \ text {maximize} \ sum_ {i= 1} ^ n v_ix_i، \ tag {p2} \\ & \ text {hase to} \ sum_ {i= 1} ^ n p_i x_i \ leq 1، \\ & \ text {and} x_i \ in \ {0،1 \}. \ end {align} $

تشغيل خوارزمية البرمجة الديناميكية لهذه المشكلة سيعطي الحل الأمثل في $ O (n) $ .هذا غير صحيح، أليس كذلك؟

Answer 1

وقت التشغيل هو $ O (NW) $ إذا كانت جميع الأوزان أعداد صحيحة .وذلك لأن جدول البرمجة الديناميكي يتم فهرسة بواسطة أوزان محتمل من مجموعات فرعية.إذا كانت جميع الأوزان أعدادا صحيحة، فمنذ أننا مهتمون فقط بضابط فرع من مجموعات فرعية تبلغ مجموعها في معظم $ W $ ، لا يوجد سوى $ W + 1 $ أوزان من مجموعات فرعية يمكن أن تهمنا.هذا هو المكان الذي يكون فيه $ W $ عامل في وقت التشغيل يأتي من.

تقسيم جميع الأوزان حسب $ W $ يحقق شيئا بالضبط.لم تغير المشكلة، لذلك الوقت المطلوب لحلها لا يزال هو نفسه تماما.