n نوع جنس مختلف وجود دارند که جنس i به اندازهی s(i) حجم اشغال میکند و به اندازهی v(i) ارزش دارد. علاوه بر این یک رابطهی ترتیب جزئی روی این جنسها تعریف شده است. این رابطه را با ≺ نشان میدهیم. رابطه ترتیب جزئی به این معناست که:
یک کولهپشتی با ظرفیت Bداریم و میخواهیم تعدادی از این اجناس را طوری انتخاب کنیم که:
اگر رابطهی ترتیب بین اجناس بهصورت درخت ریشهدار باشد و s(u)≤C;u:1…n ( C ثابت است)، یک الگوریتم چند جملهای برای حل این مسئله ارائه دهید.