دوستان لطفا مسئله زیر را حل کنید
ورودی: دو مجموعه کالا داریم که از هر کالا در هر مجموعه به یک تعداد معینی موجود است. مجموع تعداد کالاهای هر دو مجموعه با هم برابر (برابر با N ) است. به صورت فرمال ورودی به صورت زیر است:
[TABLE="width: 500, align: center"]
[TR]
[TD]تعداد
[/TD]
[TD]نام کالا[/TD]
[TD][/TD]
[TD]تعداد[/TD]
[TD]نام کالا[/TD]
[/TR]
[TR]
[TD]p[SUB]1[/SUB][/TD]
[TD]Y[SUB]1[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]1[/SUB][/TD]
[TD]X[SUB]1[/SUB][/TD]
[/TR]
[TR]
[TD]p[SUB]2[/SUB][/TD]
[TD]Y[SUB]2[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]2[/SUB][/TD]
[TD]X[SUB]2[/SUB][/TD]
[/TR]
[TR]
[TD].
.
.[/TD]
[TD].
.
.[/TD]
[TD][/TD]
[TD].
.
.[/TD]
[TD].
.
.[/TD]
[/TR]
[TR]
[TD]p[SUB]k[/SUB][/TD]
[TD]Y[SUB]k[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]m[/SUB][/TD]
[TD]X[SUB]m[/SUB][/TD]
[/TR]
[/TABLE]
که p[SUB]1[/SUB]+p[SUB]2[/SUB]+…+p[SUB]k[/SUB]=N و q[SUB]1[/SUB]+q[SUB]2[/SUB]+…+q[SUB]m[/SUB]=N
خروجی 1: می خواهیم تا تعداد زیر مجموعه های مجاز Nتایی از ترکیب این دو مجموعه (که دارای m*kعضو است) را بدست آوریم.
زیر مجموعه های مجاز Nتایی: زیرمجموعه ای که شامل N ترکیب باشد به طوری که تعداد رخداد هر کالا از هر یک از مجموعه ها برابر تعداد مشخص شده در ورودی مساله باشد ، و ترکیب تکراری در یک زیرمجموعه مجاز وجود ندارد.
در حالت کلی ما m*k حالت متفاوت از ترکیب این دو مجموعه حاصل می شود که تعداد زیرمجموعه های Nتایی آن برابر انتخاب N از mk است اما مشکل این است که همه این حالت ها مجاز نیستند.
خروجی 2: می خواهیم حداکثر احتمال حضور یک ترکیب در مجموعه مجاز را محاسبه کنیم.
بدست آوردن خروجی 2 برای من مهمتر است. ولی با بدست آوردن خروجی 1 نیز می توانم مشکلم را برطرف کنم.
حالت توسعه یافته مساله:
اگر به جای 2 مجموعه r مجموعه به صورت فوق داشته باشیم. که بخواهیم خروجی 1 و 2 را برای زیر مجموعه های Nتایی مجاز از ترکیب r مجموعه کالا را بدست آوریم.
مثال 1:
[TABLE="width: 500, align: center"]
[TR]
[TD]تعداد
[/TD]
[TD]نام کالا[/TD]
[TD][/TD]
[TD]تعداد[/TD]
[TD]نام کالا[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]a[/TD]
[TD][/TD]
[TD]2[/TD]
[TD]X[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]b[/TD]
[TD][/TD]
[TD]1[/TD]
[TD]Y[/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]Z[/TD]
[/TR]
[/TABLE]
تعداد کل ترکیبهای این دو مجموعه برابر 6 است :{Xa,Xb,Ya,Yb,Za,Zb} و تعداد زیرمجموعه های 4 تایی مجاز برابر 2 است :{Xa,Xb,Ya,Zb} و {Xa,Xb,Yb,Za} همانطور که مشاهده می کنید تعداد رخدادهای x در هر دو مجموعه برابر 2 و تعداد رخدادهای Y برابر 1 و .....
اما پاسخ خروجی 2 برابر 1 است زیرا Xa در هر دو زیرمجموعه مجاز وجود داردیا به عبارتی حداکثر احتمال حضور مربوط به عنصری است که از ترکیب حداکثر عناصر در هر مجموعه بدست آمده باشد.
ورودی: دو مجموعه کالا داریم که از هر کالا در هر مجموعه به یک تعداد معینی موجود است. مجموع تعداد کالاهای هر دو مجموعه با هم برابر (برابر با N ) است. به صورت فرمال ورودی به صورت زیر است:
[TABLE="width: 500, align: center"]
[TR]
[TD]تعداد
[/TD]
[TD]نام کالا[/TD]
[TD][/TD]
[TD]تعداد[/TD]
[TD]نام کالا[/TD]
[/TR]
[TR]
[TD]p[SUB]1[/SUB][/TD]
[TD]Y[SUB]1[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]1[/SUB][/TD]
[TD]X[SUB]1[/SUB][/TD]
[/TR]
[TR]
[TD]p[SUB]2[/SUB][/TD]
[TD]Y[SUB]2[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]2[/SUB][/TD]
[TD]X[SUB]2[/SUB][/TD]
[/TR]
[TR]
[TD].
.
.[/TD]
[TD].
.
.[/TD]
[TD][/TD]
[TD].
.
.[/TD]
[TD].
.
.[/TD]
[/TR]
[TR]
[TD]p[SUB]k[/SUB][/TD]
[TD]Y[SUB]k[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]m[/SUB][/TD]
[TD]X[SUB]m[/SUB][/TD]
[/TR]
[/TABLE]
که p[SUB]1[/SUB]+p[SUB]2[/SUB]+…+p[SUB]k[/SUB]=N و q[SUB]1[/SUB]+q[SUB]2[/SUB]+…+q[SUB]m[/SUB]=N
خروجی 1: می خواهیم تا تعداد زیر مجموعه های مجاز Nتایی از ترکیب این دو مجموعه (که دارای m*kعضو است) را بدست آوریم.
زیر مجموعه های مجاز Nتایی: زیرمجموعه ای که شامل N ترکیب باشد به طوری که تعداد رخداد هر کالا از هر یک از مجموعه ها برابر تعداد مشخص شده در ورودی مساله باشد ، و ترکیب تکراری در یک زیرمجموعه مجاز وجود ندارد.
در حالت کلی ما m*k حالت متفاوت از ترکیب این دو مجموعه حاصل می شود که تعداد زیرمجموعه های Nتایی آن برابر انتخاب N از mk است اما مشکل این است که همه این حالت ها مجاز نیستند.
خروجی 2: می خواهیم حداکثر احتمال حضور یک ترکیب در مجموعه مجاز را محاسبه کنیم.
بدست آوردن خروجی 2 برای من مهمتر است. ولی با بدست آوردن خروجی 1 نیز می توانم مشکلم را برطرف کنم.
حالت توسعه یافته مساله:
اگر به جای 2 مجموعه r مجموعه به صورت فوق داشته باشیم. که بخواهیم خروجی 1 و 2 را برای زیر مجموعه های Nتایی مجاز از ترکیب r مجموعه کالا را بدست آوریم.
مثال 1:
[TABLE="width: 500, align: center"]
[TR]
[TD]تعداد
[/TD]
[TD]نام کالا[/TD]
[TD][/TD]
[TD]تعداد[/TD]
[TD]نام کالا[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]a[/TD]
[TD][/TD]
[TD]2[/TD]
[TD]X[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]b[/TD]
[TD][/TD]
[TD]1[/TD]
[TD]Y[/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]Z[/TD]
[/TR]
[/TABLE]
تعداد کل ترکیبهای این دو مجموعه برابر 6 است :{Xa,Xb,Ya,Yb,Za,Zb} و تعداد زیرمجموعه های 4 تایی مجاز برابر 2 است :{Xa,Xb,Ya,Zb} و {Xa,Xb,Yb,Za} همانطور که مشاهده می کنید تعداد رخدادهای x در هر دو مجموعه برابر 2 و تعداد رخدادهای Y برابر 1 و .....
اما پاسخ خروجی 2 برابر 1 است زیرا Xa در هر دو زیرمجموعه مجاز وجود داردیا به عبارتی حداکثر احتمال حضور مربوط به عنصری است که از ترکیب حداکثر عناصر در هر مجموعه بدست آمده باشد.