aram_2
شنبه 27 خرداد 1391, 14:16 عصر
سلام.من این مساله رو بایستی با روش Dynamic Programming حل کنم. کسی نظری داره:
ما سه تا کوله داریم و مثلا 10 تا جنس(برای هر کوله 10 تا جنس اما با ارزش ها متفاوت).هر کدام از این اجناس دارای ارزشی هستند.اما ارزش اونها وابسته به کوله هاست:متعجب:.یعنی اینکه فایل 1 در کوله نخست یه ارزش داره و در کوله دوم ارزش دیگه و متفاوت.
هدف اینه که در هر کوله با ارزش ترین جنس قرار داده بشه.از هر جنس حداکثر یک نسخه در هر کوله می تونیم داشته باشیم.کوله ها دارای محدودیت فضایی هستند.اگه جنسی برای قرار گیری در کوله اول انتخاب بشه ممکنه همون فایل برای کوله دوم هم انتخاب بشه.من صورت بازگشتی شو می نویسم اما کدنویسی شو دوستان نظر بدن:
Tij(M)=max{ T(i+1,j(M)),T(i+1,j(M-yi))+Pij
خب در ابنجا Pij ارزش فایل i در کوله j هستش.T(i+1,j) یعنی بیشترین سود حاصل از انتخاب اجناس از i+1 تا آخرین فایل(مثلاn( و yi اندازه جنس i ام.
ما سه تا کوله داریم و مثلا 10 تا جنس(برای هر کوله 10 تا جنس اما با ارزش ها متفاوت).هر کدام از این اجناس دارای ارزشی هستند.اما ارزش اونها وابسته به کوله هاست:متعجب:.یعنی اینکه فایل 1 در کوله نخست یه ارزش داره و در کوله دوم ارزش دیگه و متفاوت.
هدف اینه که در هر کوله با ارزش ترین جنس قرار داده بشه.از هر جنس حداکثر یک نسخه در هر کوله می تونیم داشته باشیم.کوله ها دارای محدودیت فضایی هستند.اگه جنسی برای قرار گیری در کوله اول انتخاب بشه ممکنه همون فایل برای کوله دوم هم انتخاب بشه.من صورت بازگشتی شو می نویسم اما کدنویسی شو دوستان نظر بدن:
Tij(M)=max{ T(i+1,j(M)),T(i+1,j(M-yi))+Pij
خب در ابنجا Pij ارزش فایل i در کوله j هستش.T(i+1,j) یعنی بیشترین سود حاصل از انتخاب اجناس از i+1 تا آخرین فایل(مثلاn( و yi اندازه جنس i ام.