يك الگوريتم مينيمال براي حل مساله ي كوله پشتي صفر و يك چندبعدي

مساله ي كوله پشتي چندبعدي (MKP) يك مساله بهينه سازي تركيبياتي و از معروفترين مسايل برنامه ريزي صحيح است كه مي توان براي حل آن با بكارگيري از ضرايب لاگرانژ مساله را به چندين زير مساله افراز كنيم. اين جا، هرزيرمساله بيانگر يك مساله كوله پشتي صفرويك است، جايي كه، يك الگوريتم براي مساله ي كوله پشتي راكهاخيرا در ادبيات موضوع مطرح شده است و اندازه ي هسته ي مينيمال را به كارمي گيرد، تشريح مي كنيم.الگوريتم براساس برنامه ريزي پوياست و اندازه هسته به قدرنيازقابل گسترش است. عمليات مرتب سازي وكاهش متغير با روش اكتشافيكه تلاش محاسباتي را براي عمليات كاهش مي دهد، قابل اجرا هستند. يك پياده سازي ساده از اين روش و اجراي برنامهروي چندين نوع ازنمونه داده هاكه در عمل رخ مي دهند،كارآمدي روش را نشان مي دهد. روش هاي موردنظر در نرم افزار استانداردANSI-C پياده سازي وكارايي الگوريتم مينيمال با الگوريتم معروفMT2مقايسه مي شود. نتايج بدست آمدهاز آزمون ها نشانمي دهندكهالگوريتم مينيمال عملكردبهتري نسبت به الگوريتم معروفMT2براي حل مساله ي كوله پشتي صفر و يك چندبعدي دارد