جمع کدام اعداد می شود X

[hajihadi]

سلام
ستون A مبالغ واریزی بانک می باشد
عددی که در B1 وجود دارد مبلغ سفارش ما است
حال به چه صورت می توان واریزی هایی که جمع آنها مبلغ سفارش را پوشش می دهد شناسایی کرد
http://uplod.ir/xmtcjhv57mev/Bank.xlsx.htm

[khakzad]

RE: جمع کدام اعداد می شود X

سلام
ببینید فایلتون رو ندیدم
اما اگر سوالتون اینه که یک عدد حاصل چه اعدادی از یک مجموعه عدد هست........
اینو اقای اسماعیلی با ی راه حل بسیار فنی و زیبا جواب دادن
جستجو کنید پیدا می کنید

[hajihadi]

جمع کدام اعداد می شود X

با سلام و تشکر
من خیلی جستجو کردم ولی چیزی پیدا نکردم.
آقای اسماعیلی لطفاً راهنمائی کنید.

[امين اسماعيلي]

RE: جمع کدام اعداد می شود X

با درود
100000
50000
3509000
2550000
500000
این یکی از جواب های برای عدد جمع= 6,709,000
و اینم یکی دیگه :
50000
220000
3509000
450000
1860000
500000
50000
70000

حالو دوست گل من ما باید کدومشو قبول کنیم. نشستیم کلی وقت گداشتیم به امید اینکه یه جواب منحصر به فرد وجود داره . حالو میبینیم ..............

قبلا این مطلب بحث شده بود و دوستان میگفتن یه جواب بیشتر نباید پیدا بشه

[m_d6712]

RE: جمع کدام اعداد می شود X

در تحقیق در عملیات این مساله رو به عنوان Subset sum problem می شناسند. http://en.wikipedia.org/wiki/Subset_sum_problem
لینک فارسی هم دارد.!

از لحاظ پیچیدگی محاسباتی میزانی سختی این مساله NP-Complete هستش. یعنی به یک راه حل خطی قابل حل نمی باشد.
مگر از الگوریتم های جستجو، استفاده کنید. برای این منظور به ادبیات مساله partition یا مساله Subset sum problem مراجعه کنید.

از اون جایی که این مساله از ساده ترین مساله های -NP-Complete می باشد، روش های زیادی برای حل آن وجود دارد که بسیار سریع هستند. (هر جند به صورت خطی و چند جمله ای حل نمی شود)

یکی از این روش ها روش برنامه ریزی پویاست : Pseudo-polynomial time dynamic programming solution
http://www.scribd.com/doc/24761365/A-Pseudo-polynomial-Time-Algorithm-for-Subset-Sum

مساله خیلی معروف دیگری که وجود دارد مساله کوله پشتی (knapsack) هستش. در واقع Subset sum problem یک حالت خاص برای مساله کوله پشتی هست. پس شما از هر الگوریتمی برای مساله کوله پشتی برای حل مساله خودتون میتوانید استفاده کنید: https://en.wikipedia.org/wiki/Knapsack_problem
خوشبختانه لینک فارسی هم موجود است.


الگوریتم های ابتکاری هم هستند البته تضمین خاصی برای پیدا کردن جواب وحود ندارد.

در ضمن مشکلی که آقای اسمائیلی اشاره کردند با این ساختار قابل حل نمی باشد. مگر ساختار فایل رو طوری تغییر دهید که بتوان از index گذاری استفاده کرد.

[hajihadi]

جمع کدام اعداد می شود X

با سلام و تشکر از دوستان عزیز

در جواب آقای اسماعیلی می توان به این موضوع اشاره کرد که اولویت ما بر اساس تاریخ می باشد
یعنی واریزی هایی که تاریخ آن قدیمی تر است زود تر باید از چرخه خارج شوند و با رعایت این اصل که
در هر حال با کمترین تعداد واریزی این کار انجام شود.(یعنی وقتی با جمع 5 واریزی به مبلغ مورد نظر می رسیم و یا با 8 واریزی به مبلغ مورد نظر می رسیم ، 5 واریزی جواب ما است)

مجدداَ فایل را با وجود تاریخ برای دانلود گذاشتم
http://uplod.ir/e02sbk60krvb/Bank.xlsx.htm

با کمال تشکر و احترام

[امين اسماعيلي]

RE: جمع کدام اعداد می شود X

با درود
با تشکر فروان از استاد عزیزمون بابت توضیحات کامل و جامع

در اکسل یک add in وجود داره یه بخشی از اون به این مسئله میپردازه و احتمالات رو برسی میکنه و حل میکنه. solver که ما هم باید refrence هاشو از توی قسمت ویژوال البته اگر بخوایم کد نویسی شده حلش کنیم و هم خود addin رو به اکسلمون اظافه کنیم. واسه اون دسته از دوستان که کمتر اطلاعات دارن این addin داخل خود اکسل هست نیاز به دانلود از جای دیگه نداره. من کد نویسیشو و پویا کردنشو انجام دادم. و با یه کلید داده ها رو برسی میکنه. اما مشکلم فقط همین بود که چرا چند جواب داریم. و یه مشکل کوچیک دیگه که البته قابل حله لونم اینه که چون کد نویسی انجام شده وقتی فایل اکسلو میبندیم پسورد Add in سالور رو میخواد از ما که اونو هم پیدا کردم ولی هر کاری کردم نتونشتم کاری کنم که دیگه این نیاد یا خودکار وارد بشه که ما نخوایم واردش کنیم. سالور هم به این طریق عمل میکنه که اگر به جوابی رسید و مد نظر نبود میتونیم بگیم که احتمالات دیگرو انجام بده. من در ابتدا یه کلید گذاشتم که اون ععد هایی رو که از مقدار sum ما بیشتره از تو لیستمون کم بکنه تا تعداد احتمالات کم بشه و سزیعتر به جواب برسیم. سعی میکنم با توضیحاتی که استاد عزیزمون دادن و یه ذره وقت گذاشتن یه راه حل مناسب پیدا کنم.

[m_d6712]

RE: جمع کدام اعداد می شود X

با درود
با تشکر فروان از استاد عزیزمون بابت توضیحات کامل و جامع

در اکسل یک add in وجود داره یه بخشی از اون به این مسئله میپردازه و احتمالات رو برسی میکنه و حل میکنه. solver که ما هم باید refrence هاشو از توی قسمت ویژوال البته اگر بخوایم کد نویسی شده حلش کنیم و هم خود addin رو به اکسلمون اظافه کنیم. واسه اون دسته از دوستان که کمتر اطلاعات دارن این addin داخل خود اکسل هست نیاز به دانلود از جای دیگه نداره. من کد نویسیشو و پویا کردنشو انجام دادم. و با یه کلید داده ها رو برسی میکنه. اما مشکلم فقط همین بود که چرا چند جواب داریم. و یه مشکل کوچیک دیگه که البته قابل حله لونم اینه که چون کد نویسی انجام شده وقتی فایل اکسلو میبندیم پسورد Add in سالور رو میخواد از ما که اونو هم پیدا کردم ولی هر کاری کردم نتونشتم کاری کنم که دیگه این نیاد یا خودکار وارد بشه که ما نخوایم واردش کنیم. سالور هم به این طریق عمل میکنه که اگر به جوابی رسید و مد نظر نبود میتونیم بگیم که احتمالات دیگرو انجام بده. من در ابتدا یه کلید گذاشتم که اون ععد هایی رو که از مقدار sum ما بیشتره از تو لیستمون کم بکنه تا تعداد احتمالات کم بشه و سزیعتر به جواب برسیم. سعی میکنم با توضیحاتی که استاد عزیزمون دادن و یه ذره وقت گذاشتن یه راه حل مناسب پیدا کنم.

با سلام، الگوریتم های برنامه ریزی پویا به راحتی با یک تابع بازگشتی قابل پیاده سازی هستند. اگر کمی حوصله کنید میتوانید الگوریتم مورد نظر رو در قالب یک تابع در VBA بنویسید. من فکر می کنم اگر کمی جستجو کد الگوریتم به یک زبان برنامه نویسی (حتی ممکن هست به زبان VB) نوشته شده در اینترنت وجود داشته باشد.

امید وارم کمک کرده باشد.
این لینک هم بد نیست بخونید. البته به زبان انگلیسی می باشد.
http://www.or.deis.unibo.it/kp/Chapter4.pdf

[امين اسماعيلي]

RE: جمع کدام اعداد می شود X

با درود
آقا 1 روز از ما وقت گرفت با کلی دردسر آخرش به این نتیجه رسیدیم فایل که داده بودین بالای 500 حالت مختلف براش موجود هستش. حالا چیکار کنیم[hr]
با درود
البته این به خاطر بودن داده های تکراری تو ستونتون هستش که حالات مختلفی رو بوجود میاره

[hajihadi]

جمع کدام اعداد می شود X

سلام
یکی از اون 500 تا جوابم کار ما را راه می اندازد
مرسی
میشه تمام جواب ها را به ما نشان دهد تا خودمون جواب نهایی را انتخاب کنیم
باتشکر