مشكلة في حقيبة الظهر مع وجود قيود على قيم العناصر

Question

منح $ن$ العناصر مع الأوزان $w_1,...,w_n$ والقيم $v_1,...,v_n$, ، والحد الأقصى للوزن $W$, ، فإن الغرض لا يزال هو تعظيم القيمة الإجمالية للعناصر التي سيتم نقلها (مع عدم تجاوز حد الوزن).الآن، القيد الجديد هو أن يكون العنصر ذا قيمة $v_i$ يتم أخذ جميع العناصر التي قيمتها أكبر من $v_i$ يجب أن تؤخذ أيضا.(لا بأس أن نفترض أن كل شيء $v_i$انها مختلفة)

هدفي هو تحقيق ذلك في $O(ن)$ الوقت، وهذه هي محاولتي (لنفترض أن الإدخال عبارة عن مصفوفة $أ$ من الصفوف $(w_i, v_i)$):

1. حساب الوزن الإجمالي للعناصر: $W_ {\mathrm{total}}\يحصل على \sum_{i=1}^n w_i$;

2. بينما $(W_{\mathrm{total}} > W)$ يفعل:

   2.1 $p\يحصل على$ وسط القيم في $أ$;

   2.2 $R\يحصل على $ العناصر التي قيمتها أكبر من $p$;

   2.3 $L\يحصل على A\setminus R$;(العناصر التي قيمتها أقل من $p$)

   2.4 $W_R\يحصل على $ $\sum_{A[i]\in R}w_i$;

   2.5 $W_{\mathrm{total}}\يحصل على W_R$;

   2.6 $A\يحصل على R$;

3. $W\يحصل على W- W_{\mathrm{total}}$;(القدرة المتبقية)

4. كرر الخطوة 2 للمصفوفة $ل$, ، توليد المصفوفة $L'$;

5. يعود $L'\cup A$;

لاحظ أن خوارزمية إيجاد التكلفة المتوسطة للوقت الخطي.

أفترض أن تكاليف الخوارزمية الخاصة بي $O(ن)$ منذ ذلك الوقت، لكل تكرار في كل حلقة، ينخفض ​​حجم الإدخال إلى النصف - لكنني لست واثقًا من ذلك بنسبة 100٪.فهل تكلف هذه الخوارزمية حقًا وقتًا خطيًا؟وإذا لم يكن الأمر كذلك، فما هي التعديلات التي يمكن إجراؤها، أم أن هناك فكرة عامة لتصميم مثل هذه الخوارزمية التي تكلف وقتًا خطيًا؟أي مساعدة سوف تكون محل تقدير كبير!:)

Answer 1

نعم تعمل الخوارزمية الخاصة بك $O(ن)$ الوقت إذا كنت تستخدم متوسط ​​خوارزمية الوسطاء.يمكنك إثبات ذلك لنفسك من خلال النظر إلى الخوارزمية الخاصة بك وملاحظة أنه في كل حلقة يتم تقليل حجم المصفوفة التي نفكر فيها إلى النصف.ووقت تشغيل جسم الحلقة هو $O(ن)$ (إذا استخدمنا متوسط ​​الوسيطات ونسخ/تصفية المصفوفة $O(ن)$ على أي حال).الآن نحصل على المبلغ التالي:

$$\sum_{i=0}^{\log(n)} \frac{n}{2^i} \leq \sum_{i=0}^{\infty} \frac{n}{2^i } = n\cdot\sum_{i=0}^{\infty} \frac{1}{2^i} = 2n \in O(n)$$

ال $\سجل(ن)$ يأتي من حقيقة أنه يمكنك فقط تقسيم حجم المصفوفة $ سجل (ن) $ مرات في نصفين حتى تصل إلى $1$ (لأن $2^{\log(n)} = n$).يعبر كل حد من المبلغ عن تكلفة تنفيذ واحد لجسم الحلقة.