سوال 12

در راهروی نقاشی‌های ارزشمند یک موزه، $n$ تابلوی نقاشی با شماره‌های ۱ تا $n$ در یک ردیف کنار هم به دیوار آویخته شده‌اند. یک سارق می‌خواهد از این موزه دزدی کند. او می‌داند ارزش تابلوی $i$ام برابر $v_i$ است. به دلیل نزدیک بودن تابلوها به هم، اگر سارق تابلوی شماره $i$ را از دیوار بکند، دو تابلوی مجاور آن با شماره‌های $i-1$ و $i+1$ (در صورت وجود) پاره و بی‌ارزش می‌گردند.

هدف سارق سرقت تعدادی از تابلوهای موزه است که مجموع ارزش تابلوهای سرقتی (سود وی) بیشینه شود. $P(i)$ را برابر بیشینه‌ی سود سارق تعریف می‌کنیم در حالتی که فقط تابلوهای شماره‌ی ۱ تا $i$ قابل سرقت هستند. در این صورت کدام رابطه‌ی زیر برقرار است؟ (فرض کنید $P(۰)=۰$ و $P(-۱)=۰$ قرارداد شده است. منظور از $max( a,b)$، مقدار بیشینه‌ی $a$ و $b$ است)

1. $P(i)= max (v_i + P(i-1), P(i-2))$
2. $P(i)= v_i + max (P(i-1), P(i-2))$
3. $P(i)= P(i-1) + max (v_i, P(i-2))$
4. $P(i)= P(i-2) + max (v_i, P(i-1))$
5. $P(i)= max(v_i + P(i-2), P(i-1))$

• سوال بعد
• سوال قبل