مسئله کوله پشتی چیست ؟ بررسی کامل KnapSack Problem

مسئله کوله پشتی چیست ؟ یکی از مسائل معروف در هوش مصنوعی ، تحقیق در عملیات و طراحی الگوریتم است که در ادامه به بررسی کامل آن می پردازیم.

هدف از مسئله کوله پشتی ، یافتن ماکزیمم ارزش از اجسامی است که در یک کوله پشتی با ظرفیت محدود میتوان قرار داد.

تعریف مسئله کوله پشتی به بیان ساده :

مجموعه ای از وسایل داریم که آنها را با اعداد 1 تا n شماره گذازی میکنیم.

هر کدوم از وسایل وزن خاص خود را دارد که وزن آنها را نیز با علامت های w1 تا wn نشان میدهیم.

هر کدام از وسایل ، ارزش خاص خود را دارد که ارزش اشیا را با v1 تا vn نشان میدهیم.

• پس شی شماره 1 دارای وزن w1 و ارزش v1 می باشد،
• شی شماره 2 دارای وزن w2 و ارزش v2 می باشد،
• شی شماره 3 دارای وزن w3 و ارزش v3 می باشد.