یافتن هزینه ی سطر بهینه

[eama183]

سلام دوستان
من تا چهرشنبه دوتا امتحان سخت دارم :افسرده:و متاسفانه این برنامه هم آخرین مهلتش چهارشنبه ست:گریه:،لطفا اگه کسی می تونه کمک کنه خواهش می کنم.

مسئله:
فرض کنید یک متن ورودی که شامل ان کلمه با طول های L1و....LN است داده شده است.طول هر کلمه بنا بر تعریف برابر با تعداد کاراکترهای به کار رفته در آن است.می خاهیم این متن را به گونه ای سطربندی کنیم که در هر سطر حداکثر ام کاراکتر قرار بگیرد.بین هر 2کلمهiو i+1 که در یک سطر قرار میگیزند یک کاراکتر خالی درج میکنیم.فضای اضافی باقی مانده در انتهای هر سطر را نیز با کاراکتر های خالی پر میکنیم. بنابراین اگر کلمات i تا j در یک سطر قرار گیرند تعداد کاراکتر های خالی اضافی در انتهای سطر برابر خواهد بود با :

m-j+i-∑L
راه های مختلفی برای تقسیم یک پاراگراف به چند سطر وجود دارد ولی سعی ما این است که سطرهای پاراگراف تا حد ممکن چشم نواز باشد یک روش مناسب این است که برای هر سطر یک هزینه در نظر بگیریم که برابر با مکعب تعداد فضاهای خالی در آن سطر است و سعی میکنیم مجموع این هزینه ها را به حداقل برسانیم .برای اینکه فضاهای خالی اضافی در آخرین سطر تاثیری در محاسبات نداشته باشند هزینه ی آخرین سطر را برابر 0 تعریف میکنیم. به عبارت دیگر اگر هزینه سطری که شامل کلمات آی تا جی است را :
LINECOST(i,j)=(m-j+i-∑L)^3
هزینه ی سطر بندی یک پاراگراف برابر خواهد بود با مجموع هزینه های مربوط به تمامی سطرهای آن پاراگراف .یک جواب بهینه عبارت است از تقسیم ان کلمه به چند سطر طوری که هزینه های سطر بندی کلمات کمترین مقدار ممکن را داشته باشند.

الف)فرض کنید c(j) برابر با هزینه ی سطربندی بهینه ی کلمات 1 تاj باشد.مقدار c(j) را به صورت بازگشتی (تابع لاین کست) تعریف کنید.
ب)با استفاده از برنامه سازی پویا یک الگوریتم کارا برای محاسبه مقدار جواب بهینه و خود جواب بهینه ارایه کنید.
فایل ورودی
در سطر اول از فایل ورودی مقدار ان(تعداد کلمات ) در سطر 2 مقدار ام (اندازه ی هر سطر) و در ان سطر بعدی عددهای ال1وال2و.....وال ان(طول کلمات ) می ایند.


فایل خروجی
در سطر اول از فایل خروجی مقدار جواب بهینه (هزینه سطر بندی بهینه کلمات ) می اید. در سطرهای بعدی و در هر سطر یک سه تایی (آی و جی و کا) می آید که نشان می دهد کلمات آی تا جی در سطر کا قرار گرفته اند.

[qwerty11]

اگر مسئله رو درست فهمیده باشم این شکلی میشه حلش کرد :


اگر a[i] I رو برابر جواب بهینه برای رشته های i تا n به شرطی که i ، رشته ی اول سطر باشه میشه گفت :

فرض کن یه تابع هم داریم که هزینه ی یه سطر رو که رشته های i تا ل توش هستن رو برمیگردونه. اسم این تابه رو میزاریم f(i,j) I .

حالا واسه a[0] I یه جواب ممکن اینه که فقط رشته ی اول توی سطر بیاد. تو این حالت هزینه ی ما برابر a[1] + f(0,0) I خواهد بود. یه جواب دیگه هم اینه که رشته ی اول و رشته ی دوم توی سطر بیان (البته در صورت امکان) . تو این حالت a[0] I برابر a[2] + f(0,1) I خواهد بود و به همین ترتیب ...

توجه : هرچی I تو متن نوشتم رو حذفش کن !!! نیست که خیلی پیشرفتست مجبور شدم واسه خوانایی این کارو انجام بدم.

اگه نفهمیدی دیگه نمیدونم چجوری بگم :لبخند::لبخند:

[eama183]

از اینکه کمک کردید واقعا ممنونم.البته فکر کنم یه فرمول بعد از سطر2باید باشه مثل اینکه فراموش کردین.
مشکل من اینه که برای تعریف بازگشتی تابع linecost مشکل دارم.اگر بتونیم یه نعریف بازگشتی براش بدیم مشکل حله.اگه بازم می تونید لطفا کمک کنید.
باتشکر

[qwerty11]

از اینکه کمک کردید واقعا ممنونم.البته فکر کنم یه فرمول بعد از سطر2باید باشه مثل اینکه فراموش کردین.
مشکل من اینه که برای تعریف بازگشتی تابع linecost مشکل دارم.اگر بتونیم یه نعریف بازگشتی براش بدیم مشکل حله.اگه بازم می تونید لطفا کمک کنید.
باتشکر

سلام !!! فکر کنم اون تعریفی که من دادم بازگشتی بود !! اما به هر حال این کد شاید کمکت کنه


long calc(int i){



if(i==n) return 0;
if(a[i]!=MAX) return a[i];
for(int j=i; j<n && m>=sum[j+1]-sum[i]+j-i; j++)
a[i]=min(a[i],calc(j+1)+f(i,j));
return a[i];
}


که تو این تابع sum[i] I مجموع طول رشته های صفر تا i-1 هستش !!
MAX هم یه مقدار خیلی بزرگه که مقدار اولیه آرایه a هستش !!!
تابع f همون تابع linecost تو هستش به صورت زیر تعریف میکنیمش :



long f(int i,int j){
return pow(m-sum[j+1]+sum[i]-j+i, 3);
}

منظورت از تعریف تابع linecost به صورت بازگشتی چیه !!؟؟؟ تابع linecost رو همونطور که گفتم میشه با O(1) I به دست آوردش !!!

[eama183]

خیلی ممنون مهندس:تشویق:
خودمم روش کار میکنم یه چیزی براش می فرستم