البرمجة الديناميكية - اللص الاختلاف Probem

Question

لقد واجهت البرمجة الديناميكية المشكلة التي هو الاختلاف من لص واحد.

أقول أنت لص و يتم إعطاء عدد من المنازل في صف واحد عليك أن تسرق :

$$House_1,House_2 \النقاط House_N$$

مع كل بيت من وجود القيم التالية : $$(x_i \geq y_i \geq z_i \gt0)$$

لك الربح X إذا كنت سرقة منزل ولكن لا المجاورة المنازل.

لك الربح Y إذا كنت سرقة منزل ، واحد بالضبط المجاورة المنازل.

لك الربح Z إذا كنت سرقة منزل ، سواء المجاورة المنازل.

الحالات مع المنازل A-B-C ليكون :

$$الربح(001)=0+0+C_x$$ $$الربح(101)=A_x+0+C_x$$ $$الربح(110)=A_y+B_y+0$$ $$الربح(111)=A_y+B_z+C_y$$

حيث 1 لتقف على سرقة المنزل 0 لعدم سرقة المنزل

من الواضح أنه لا يمكنك الاستفادة من Z قيمة أول و آخر البيت و كل مجموعة من القيم العشوائية.

والسؤال الآن هو :الذي يضم يجب أن روب للحصول على أقصى قدر من الربح ؟

بلدي المسألة الرئيسية هي أنني لا يمكن إنشاء قاعدة حال لهذه المشكلة.

في البداية اعتقدت خلق ن*م مع مجموعة M يجري قدر ممكن من المنازل لا يمكن أن تسلب من 0-N عند كل بيت ليس سرق و أعتقد مثل :سرقته - لا تسرق ولكن جاء مع أي شيء.

أي نصائح أو توجيهات سيكون موضع تقدير.

شكرا مقدما.

Answer 1

بالنسبة $i=1,\النقاط ، ن$, ، $r \في \{S,R,B\}$ تعريف $OPT[i,r]$ كما أقصى قدر من الأرباح التي يمكن الحصول عليها من خلال سرقة مناسبة فرعية من أول $i$ المنازل مع القيود التالية:

• إذا $x=S$ (كما في Sكيب) ثم البيت $i$ يجب أن لا يكون سرقة.
• إذا $x=R$ ثم البيت $i$ يجب أن يكون Robbed بينما البيت $i+1$ لن يكون سرق (لتجنب حالة تمييز في وقت لاحق ونحن ندعي ذلك المنزل $i+1$ موجود حتى عند $i=N$).
• إذا $x=B$ ثم بoth البيت $i$ و البيت $i+1$ تحتاج إلى أن يكون سرقة.

بالنسبة $i=1$ لديك $OPT[1,S] = 0$, $OPT[1,R] = x_1$, $OPT[1,B] = y_1$.

بالنسبة $i>1$ لديك:$$ تختار[i, S] = \ماكس\{ تختار[i-1, S] واختاري[i-1, R] \}, $$ $$ تختار[i, R] = \ماكس\{ x_i + تختار[i-1, S], y_i + تختار[i-1 ، B] \}, $$ $$ تختار[i, B] = \ماكس\{ y_i + تختار[i-1, S], z_i + تختار[i-1 ، B] \}.$$

الأمثل الربح ثم:$\ماكس\{تختار[N, S] واختاري[N, R] \}$ و يمكن حسابها في $O(N)$ عموما الوقت باستخدام الصيغ أعلاه.