کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959503 | 1445950 | 2017 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
ترجمه فارسی عنوان
یک الگوریتم برنامه ریزی دینامیکی پویا برای کمترین هزینه بسته بندی کوله پشتی کم هزینه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بهینه سازی ترکیبی، بسته بندی کوله پشتی حداکثر، پوشش کم پشتی، برنامه نویسی دینامیک، برنامه ریزی عدد صحیح
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
Given a set of items with profits and weights and a knapsack capacity, we study the problem of finding a maximal knapsack packing that minimizes the profit of the selected items. We propose an effective dynamic programming (DP) algorithm which has a pseudo-polynomial time complexity. We demonstrate the equivalence between this problem and the problem of finding a minimal knapsack cover that maximizes the profit of the selected items. In an extensive computational study on a large and diverse set of benchmark instances, we demonstrate that the new DP algorithm outperforms a state-of-the-art commercial mixed-integer programming (MIP) solver applied to the two best performing MIP models from the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 262, Issue 2, 16 October 2017, Pages 438-448
Journal: European Journal of Operational Research - Volume 262, Issue 2, 16 October 2017, Pages 438-448
نویسندگان
Fabio Furini, Ivana LjubiÄ, Markus Sinnl,