مشكلة حقيبة الظهر

ترتبط صعوبة مسألة حقيبة الظهر (NP-hardness) بالنماذج الحسابية التي يكون فيها حجم الأعداد الصحيحة مهمًا (مثل آلة تورينج ). في المقابل، تحسب أشجار القرار كل قرار كخطوة واحدة. وقد أوضح دوبكين وليبتون ^{[ 13 ]}${\displaystyle {1 \over 2}n^{2}}$الحد الأدنى لأشجار القرار الخطية لمسألة حقيبة الظهر، أي الأشجار التي تختبر فيها عقد القرار إشارة الدوال الخطية . ^{[ 14 ]} وقد عُمِّم هذا ليشمل أشجار القرار الجبرية بواسطة ستيل وياو. ^{[ 15 ]} إذا كانت عناصر المسألة أعدادًا حقيقية أو نسبية ، فإن الحد الأدنى لشجرة القرار يمتد إلى نموذج آلة الوصول العشوائي الحقيقية مع مجموعة تعليمات تتضمن جمع وطرح وضرب الأعداد الحقيقية، بالإضافة إلى المقارنة والقسمة أو الباقي ("الجزء الصحيح"). ^{[ 16 ]} يغطي هذا النموذج خوارزميات أكثر من نموذج شجرة القرار الجبرية، لأنه يشمل الخوارزميات التي تستخدم الفهرسة في الجداول. ومع ذلك، في هذا النموذج، تُحسب جميع خطوات البرنامج، وليس القرارات فقط. قدم ماير أوف دير هايد ^{[ 17 ]} حدًا أعلى لنموذج شجرة القرار، حيث أظهر أنه لكل n توجد شجرة قرار خطية ^بعمق O ( n⁴ ) تحل مسألة مجموع المجموعات الجزئية التي تحتوي على n عنصرًا. لاحظ أن هذا لا يعني وجود حد أعلى للخوارزمية التي ينبغي أن تحل المشكلة لأي قيمة معطاة لـ n .

لا تفرض مسألة حقيبة الظهر غير المحدودة ( UKP ) أي قيود على عدد نسخ كل نوع من العناصر. بالإضافة إلى ذلك، نفترض هنا أن${\displaystyle x_{i}>0}$

${\displaystyle m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)}$

رهناً بـ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq w'}$و${\displaystyle x_{i}>0}$

لاحظ ذلك${\displaystyle m[w]}$له الخصائص التالية:

1.${\displaystyle m[0]=0\,\!}$(مجموع العناصر الصفرية، أي مجموع المجموعة الفارغة ).

2.${\displaystyle m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])}$ ،${\displaystyle w_{i}\leq w}$، أين${\displaystyle v_{i}}$قيمة${\displaystyle i}$النوع -th من العناصر.

تحتاج الخاصية الثانية إلى شرح مفصل. كيف نحصل على الوزن أثناء تشغيل هذه الطريقة؟${\displaystyle w}$لا يوجد سوى${\displaystyle i}$الطرق والأوزان السابقة هي${\displaystyle w-w_{1},w-w_{2},...,w-w_{i}}$حيث يوجد إجمالي${\displaystyle i}$أنواع مختلفة من العناصر (بمعنى مختلف، نعني أن الوزن والقيمة ليسا متطابقين تمامًا). إذا عرفنا قيمة كل من هذه القيم${\displaystyle i}$بعد تحديد العناصر والقيمة القصوى المرتبطة بها سابقًا، نقوم بمقارنتها ببعضها البعض ونحصل في النهاية على القيمة القصوى، وبذلك نكون قد انتهينا.

هنا، تُعتبر القيمة القصوى للمجموعة الفارغة صفرًا. جدولة النتائج من${\displaystyle m[0]}$حتى${\displaystyle m[W]}$يُعطي الحل. بما أن حساب كل${\displaystyle m[w]}$يتضمن فحصًا على الأكثر${\displaystyle n}$العناصر، وهناك على الأكثر${\displaystyle W}$قيم${\displaystyle m[w]}$لحساب وقت تشغيل حل البرمجة الديناميكية، يكون${\displaystyle O(nW)}$التقسيم${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$يُعد حساب القاسم المشترك الأكبر طريقة لتحسين وقت التشغيل.

حتى لو كان P≠NP ، فإن${\displaystyle O(nW)}$لا يتعارض التعقيد مع حقيقة أن مسألة حقيبة الظهر هي مسألة كاملة من فئة NP ، لأن${\displaystyle W}$على عكس${\displaystyle n}$، ليس متعدد الحدود بالنسبة لطول المدخلات في المسألة. طول${\displaystyle W}$المدخلات في المسألة تتناسب مع عدد البتات في${\displaystyle W}$،${\displaystyle \log W}$، وليس لـ${\displaystyle W}$ومع ذلك، بما أن وقت التشغيل هذا هو شبه متعدد الحدود ، فإن هذا يجعل (نسخة القرار من) مشكلة حقيبة الظهر مشكلة NP-كاملة ضعيفة .

مشكلة حقيبة الظهر 0-1

يُنفذ حل مماثل للبرمجة الديناميكية لمسألة حقيبة الظهر 0-1 في وقت شبه متعدد الحدود. افترض${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$هي أعداد صحيحة موجبة تمامًا. عرّف${\displaystyle m[i,w]}$أن تكون القيمة القصوى التي يمكن تحقيقها بوزن أقل من أو يساوي${\displaystyle w}$باستخدام عناصر تصل إلى${\displaystyle i}$(أولاً${\displaystyle i}$أغراض).

يمكننا أن نحدد${\displaystyle m[i,w]}$بشكل متكرر كما يلي: (التعريف أ)

• ${\displaystyle m[0,\,w]=0}$
• ${\displaystyle m[i,\,w]=m[i-1,\,w]}$لو${\displaystyle w_{i}>w\,\!}$(الوزن الجديد يتجاوز الحد الأقصى للوزن المسموح به حاليًا)
• ${\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}$لو${\displaystyle w_{i}\leqslant w}$.

ويمكن إيجاد الحل عن طريق الحساب${\displaystyle m[n,W]}$وللقيام بذلك بكفاءة، يمكننا استخدام جدول لتخزين العمليات الحسابية السابقة.

فيما يلي رمز زائف للبرنامج الديناميكي:

// مدخل:// القيم (المخزنة في المصفوفة v)// الأوزان (مخزنة في المصفوفة w)// عدد العناصر المميزة (ن)// سعة حقيبة الظهر (واط)// ملاحظة: يُفترض أن المصفوفة "v" والمصفوفة "w" تخزنان جميع القيم ذات الصلة بدءًا من الفهرس 1.array m [ 0. . n , 0. . W ];لكل j من 0 إلى W ، نفّذ ما يلي :m [ 0 , j ] := 0for i from 1 to n do :m [ i , 0 ] := 0for i from 1 to n do :لكل j من 1 إلى W ، نفّذ ما يلي :إذا كان w [ i ] > j، فإن :m [ i , j ] := m [ i -1 , j ]آخر :m [ i , j ] := max ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])

وبالتالي، سيتم تشغيل هذا الحل في${\displaystyle O(nW)}$الوقت و${\displaystyle O(nW)}$المساحة. (إذا كنا نحتاج فقط إلى القيمة m[n,W]، فيمكننا تعديل الكود بحيث يكون مقدار الذاكرة المطلوبة هو O(W) الذي يخزن السطرين الأخيرين من المصفوفة "m".)

لكن إذا تعمقنا في الأمر خطوة أو خطوتين إضافيتين، فسندرك أن الطريقة ستعمل في الفترة الزمنية بين${\displaystyle O(nW)}$و${\displaystyle O(2^{n})}$من التعريف (أ) ، نعلم أنه لا حاجة لحساب جميع الأوزان عندما يكون عدد العناصر والعناصر المختارة ثابتة. بمعنى آخر، يحسب البرنامج أعلاه أكثر من اللازم لأن الوزن يتغير من 0 إلى W بشكل متكرر. من هذا المنطلق، يمكننا برمجة هذه الطريقة بحيث تعمل بشكل تكراري.

// مدخل:// القيم (المخزنة في المصفوفة v)// الأوزان (مخزنة في المصفوفة w)// عدد العناصر المميزة (ن)// سعة حقيبة الظهر (واط)// ملاحظة: يُفترض أن المصفوفة "v" والمصفوفة "w" تخزنان جميع القيم ذات الصلة بدءًا من الفهرس 1.حدد القيمة [ ن ، W ]قم بتهيئة جميع القيم [ i , j ] = -1عرّف m := ( i , j ) // عرّف الدالة m بحيث تمثل القيمة القصوى التي يمكننا الحصول عليها في ظل الشرط التالي: استخدام أول i عنصر، والحد الأقصى للوزن الإجمالي هو j{إذا كان i == 0 أو j <= 0 فإن :القيمة [ i , j ] = 0يعودإذا كانت قيمة ( القيمة [ i -1 , j ] تساوي -1 ) فإن : // لم يتم حساب m[i-1, j]، لذا يجب استدعاء الدالة mم ( i -1 ، j )إذا كان w [ i ] > j ، فهذا يعني : // لا يمكن وضع العنصر في الحقيبةالقيمة [ i , j ] = القيمة [ i -1 , j ]آخر :إذا كانت قيمة ( القيمة [ i -1 ، j - w [ i ]] تساوي -1 ) فإن : // لم يتم حساب m[i-1، jw[i]]، لذا يجب استدعاء الدالة mm ( i -1 , j - w [ i ])القيمة [ i , j ] = الحد الأقصى ( القيمة [ i -1 , j ], القيمة [ i -1 , j - w [ i ]] + v [ i ])}تشغيل m ( n , W )

على سبيل المثال، هناك 10 أصناف مختلفة والحد الأقصى للوزن هو 67. لذا، $${\displaystyle {\begin{aligned}&w[1]=23,w[2]=26,w[3]=20,w[4]=18,w[5]=32,w[6]=27,w[7]=29,w[8]=26,w[9]=30,w[10]=27\\&v[1]=505,v[2]=352,v[3]=458,v[4]=220,v[5]=354,v[6]=414,v[7]=498,v[8]=545,v[9]=473,v[10]=543\\\end{aligned}}}$$ إذا استخدمت الطريقة المذكورة أعلاه لحساب${\displaystyle m(10,67)}$ستحصل على هذا، باستثناء المكالمات التي تنتج${\displaystyle m(i,j)=0}$: $${\displaystyle {\begin{aligned}&m(10,67)=1270\\&m(9,67)=1270,m(9,40)=678\\&m(8,67)=1270,m(8,40)=678,m(8,37)=545\\&m(7,67)=1183,m(7,41)=725,m(7,40)=678,m(7,37)=505\\&m(6,67)=1183,m(6,41)=725,m(6,40)=678,m(6,38)=678,m(6,37)=505\\&m(5,67)=1183,m(5,41)=725,m(5,40)=678,m(5,38)=678,m(5,37)=505\\&m(4,67)=1183,m(4,41)=725,m(4,40)=678,m(4,38)=678,m(4,37)=505,m(4,35)=505\\&m(3,67)=963,m(3,49)=963,m(3,41)=505,m(3,40)=505,m(3,38)=505,m(3,37)=505,m(3,35)=505,m(3,23)=505,m(3,22)=458,m(3,20)=458\\&m(2,67)=857,m(2,49)=857,m(2,47)=505,m(2,41)=505,m(2,40)=505,m(2,38)=505,m(2,37)=505,m(2,35)=505,m(2,29)=505,m(2,23)=505\\&m(1,67)=505,m(1,49)=505,m(1,47)=505,m(1,41)=505,m(1,40)=505,m(1,38)=505,m(1,37)=505,m(1,35)=505,m(1,29)=505,m(1,23)=505\\\end{aligned}}}$$

إضافةً إلى ذلك، يمكننا كسر الاستدعاء الذاتي وتحويله إلى شجرة. ثم يمكننا حذف بعض الأوراق واستخدام الحوسبة المتوازية لتسريع تنفيذ هذه الطريقة.

لإيجاد المجموعة الفرعية الفعلية من العناصر، بدلاً من قيمتها الإجمالية فقط، يمكننا تشغيل هذا بعد تشغيل الدالة أعلاه:

/*** تُرجع هذه الدالة مؤشرات عناصر حقيبة الظهر المثلى.* i: يمكننا تضمين العناصر من 1 إلى i في حقيبة الظهر* j: أقصى وزن للحقيبة*/دالة حقيبة الظهر ( i : عدد صحيح ، j : عدد صحيح ) : مجموعة < عدد صحيح > {إذا كان i == 0 فإن :يعود {}إذا كان m [ i , j ] > m [ i -1 , j ] فإن :return { i } ∪ knapsack ( i -1 , j - w [ i ])آخر :أعد حقيبة الظهر ( i -1 ، j )}حقيبة الظهر ( ن ، و )

هناك خوارزمية أخرى لمسألة حقيبة الظهر 0-1، تم اكتشافها عام 1974 ^{[ 23 ]} وتُسمى أحيانًا "اللقاء في المنتصف" نظرًا لتشابهها مع خوارزمية تحمل اسمًا مشابهًا في علم التشفير ، وهي خوارزمية أسية بالنسبة لعدد العناصر المختلفة، ولكنها قد تكون أفضل من خوارزمية البرمجة الديناميكية عندما${\displaystyle W}$كبيرة مقارنة بـ n . على وجه الخصوص، إذا كان${\displaystyle w_{i}}$إذا كانت الأعداد غير سالبة ولكنها ليست أعدادًا صحيحة، فلا يزال بإمكاننا استخدام خوارزمية البرمجة الديناميكية عن طريق التحجيم والتقريب (أي باستخدام حسابات النقطة الثابتة )، ولكن إذا كانت المسألة تتطلب${\displaystyle d}$دقة تصل إلى أرقام كسرية للوصول إلى الإجابة الصحيحة،${\displaystyle W}$سيحتاج إلى تعديل الحجم بواسطة${\displaystyle 10^{d}}$وسيتطلب ذلك خوارزمية البرمجة الديناميكية${\displaystyle O(W10^{d})}$الفضاء و${\displaystyle O(nW10^{d})}$وقت.

خوارزمية " اللقاء في المنتصف" هي : المدخلات: مجموعة من العناصر ذات الأوزان والقيم. المخرجات: أكبر قيمة مجمعة لمجموعة فرعية. قسّم المجموعة {1... n } إلى مجموعتين A و B متساويتين تقريبًا في الحجم احسب أوزان وقيم جميع المجموعات الفرعية لكل مجموعة لكل مجموعة جزئية من A، أوجد المجموعة الجزئية من B ذات القيمة الأكبر بحيث يكون الوزن الإجمالي أقل من W تابع أكبر قيمة إجمالية تم رصدها حتى الآن

تأخذ الخوارزمية${\displaystyle O(2^{n/2})}$يؤدي استخدام المساحة، والتنفيذ الفعال للخطوة 3 (على سبيل المثال، فرز المجموعات الفرعية من B حسب الوزن، واستبعاد المجموعات الفرعية من B التي يزيد وزنها عن وزن المجموعات الفرعية الأخرى من B ذات القيمة الأكبر أو المساوية، واستخدام البحث الثنائي للعثور على أفضل تطابق) إلى وقت تشغيل قدره${\displaystyle O(n2^{n/2})}$وكما هو الحال مع هجوم "الالتقاء في المنتصف" في علم التشفير، فإن هذا يُحسّن من...${\displaystyle O(n2^{n})}$وقت تشغيل نهج القوة الغاشمة الساذج (فحص جميع المجموعات الفرعية من${\displaystyle \{1...n\}}$، على حساب استخدام مساحة أسية بدلاً من مساحة ثابتة (انظر أيضًا خطوة صغيرة وخطوة عملاقة ). يوفر التحسين الحالي لخوارزمية الالتقاء في المنتصف، باستخدام رؤى من خوارزمية شرويبل وشامير لمجموع المجموعات الجزئية، كنتيجة طبيعية لخوارزمية عشوائية لمسألة الحقيبة تحافظ على${\displaystyle O^{*}(2^{n/2})}$(حتى عوامل متعددة الحدود) وقت التشغيل ويقلل من متطلبات المساحة إلى${\displaystyle O^{*}(2^{0.249999n})}$(انظر ^{[ 24 ]} النتيجة 1.4). في المقابل، تعمل أفضل خوارزمية حتمية معروفة في${\displaystyle O^{*}(2^{n/2})}$الوقت مع تعقيد مكاني أسوأ قليلاً من${\displaystyle O^{*}(2^{n/4})}$[ ^{25 ]​}

كما هو الحال في معظم مسائل NP-complete، قد يكفي إيجاد حلول عملية حتى وإن لم تكن مثالية. مع ذلك، يُفضّل أن يكون التقريب مصحوبًا بضمان الفرق بين قيمة الحل المُكتشف وقيمة الحل الأمثل.

كما هو الحال مع العديد من الخوارزميات المفيدة ولكن المعقدة حسابيًا، فقد أُجريت أبحاثٌ مكثفةٌ حول إنشاء وتحليل الخوارزميات التي تُقارب الحل. تُعدّ مسألة حقيبة الظهر، على الرغم من كونها مسألةً صعبةً حسابيًا (NP-Hard)، واحدةً من مجموعةٍ من الخوارزميات التي لا يزال من الممكن تقريبها إلى أي درجةٍ مُحددة. هذا يعني أن المسألة لها مخطط تقريبٍ زمنيٍّ متعدد الحدود. وبشكلٍ أدق، فإن مسألة حقيبة الظهر لها مخطط تقريبٍ زمنيٍّ متعدد الحدود بالكامل (FPTAS). ^{[ 26 ]}

يتم إدخال خوارزمية FPTAS : ε ∈ (0,1) قائمة A تحتوي على n عنصرًا، محددة بقيمها،${\displaystyle v_{i}}$، والأوزان الناتجة : S' حل FPTAS P := الحد الأقصى${\displaystyle \{v_{i}\mid 1\leq i\leq n\}}$ // أعلى قيمة للعنصر K := ε${\displaystyle {\frac {P}{n}}}$لكل i من 1 إلى n نفّذ${\displaystyle v'_{i}}$:=${\displaystyle \left\lfloor {\frac {v_{i}}{K}}\right\rfloor }$نهاية لـأعد الحل، S'، باستخدام${\displaystyle v'_{i}}$القيم في البرنامج الديناميكي الموضح أعلاه

يمكن تسهيل حل مشكلة الحقيبة غير المحدودة عن طريق التخلص من العناصر التي لن تكون مطلوبة أبدًا. بالنسبة لعنصر معين${\displaystyle i}$لنفترض أننا نستطيع إيجاد مجموعة من العناصر${\displaystyle J}$بحيث يكون وزنها الإجمالي أقل من وزن${\displaystyle i}$وقيمتها الإجمالية أكبر من قيمة${\displaystyle i}$. ثم${\displaystyle i}$لا يمكن أن يظهر في الحل الأمثل، لأنه يمكننا دائمًا تحسين أي حل محتمل يحتوي على${\displaystyle i}$عن طريق الاستبدال${\displaystyle i}$مع المجموعة${\displaystyle J}$لذلك، يمكننا تجاهل${\displaystyle i}$العنصر رقم - بشكل عام. في مثل هذه الحالات،${\displaystyle J}$يقال إنه يهيمن${\displaystyle i}$(لاحظ أن هذا لا ينطبق على مسائل حقيبة الظهر المحدودة، حيث قد نكون قد استنفدنا العناصر بالفعل في${\displaystyle J}$.)

يُتيح لنا إيجاد علاقات الهيمنة تقليص حجم فضاء البحث بشكل ملحوظ. توجد عدة أنواع مختلفة من علاقات الهيمنة ، ^{[ 11 ]} والتي تُحقق جميعها متباينة على النحو التالي:

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$، و${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$بالنسبة للبعض${\displaystyle x\in Z_{+}^{n}}$

أين ${\displaystyle \alpha \in Z_{+}\,,J\subsetneq N}$و${\displaystyle i\not \in J}$المتجه${\displaystyle x}$يشير إلى عدد نسخ كل عضو من أعضاء${\displaystyle J}$.

الهيمنة الجماعية

ال${\displaystyle i}$العنصر رقم -th يهيمن عليه بشكل جماعي${\displaystyle J}$، مكتوبة على النحو التالي${\displaystyle i\ll J}$إذا كان الوزن الإجمالي لمجموعة معينة من العناصر في${\displaystyle J}$أقل من w _i وقيمتهما الإجمالية أكبر من v _i . رسميًا،${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}}$و${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}}$بالنسبة للبعض${\displaystyle x\in Z_{+}^{n}}$، أي${\displaystyle \alpha =1}$يُعدّ التحقق من هذه الهيمنة أمرًا صعبًا حسابيًا، لذا لا يمكن استخدامه إلا مع أسلوب البرمجة الديناميكية. في الواقع، يُعادل هذا حلّ مسألة اتخاذ قرار حقيبة ظهر أصغر حيث${\displaystyle V=v_{i}}$،${\displaystyle W=w_{i}}$وتقتصر العناصر على${\displaystyle J}$.

هيمنة العتبة

ال${\displaystyle i}$العنصر رقم -th هو العنصر الذي يهيمن عليه العتبة بواسطة${\displaystyle J}$، مكتوبة على النحو التالي${\displaystyle i\prec \prec J}$، إذا كان هناك عدد من نسخ${\displaystyle i}$تهيمن عليها${\displaystyle J}$رسميًا،${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$، و${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$بالنسبة للبعض${\displaystyle x\in Z_{+}^{n}}$و${\displaystyle \alpha \geq 1}$هذا تعميم لمفهوم الهيمنة الجماعية، الذي طُرح لأول مرة في ^{[ 18 ]} واستُخدم في خوارزمية EDUK. أصغر هذه${\displaystyle \alpha }$يحدد عتبة العنصر${\displaystyle i}$، مكتوب ${\displaystyle t_{i}=(\alpha -1)w_{i}}$في هذه الحالة، يمكن أن يحتوي الحل الأمثل على أكثر من${\displaystyle \alpha -1}$نسخ من${\displaystyle i}$.

الهيمنة المتعددة

ال${\displaystyle i}$العنصر رقم -th يهيمن عليه عنصر واحد بشكل متعدد${\displaystyle j}$، مكتوبة على النحو التالي${\displaystyle i\ll _{m}j}$، لو${\displaystyle i}$تهيمن عليها بعض نسخ${\displaystyle j}$رسميًا،${\displaystyle w_{j}\,x_{j}\ \leq w_{i}}$، و${\displaystyle v_{j}\,x_{j}\ \geq v_{i}}$بالنسبة للبعض${\displaystyle x_{j}\in Z_{+}}$أي${\displaystyle J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor }$يمكن استخدام هذه الهيمنة بكفاءة أثناء المعالجة المسبقة لأنه يمكن اكتشافها بسهولة نسبية.

هيمنة الوحدات النمطية

يترك${\displaystyle b}$كن أفضل عنصر ، أي${\displaystyle {\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,}$للجميع${\displaystyle i}$هذا هو العنصر ذو أعلى كثافة قيمة.${\displaystyle i}$العنصر رقم - يهيمن عليه عنصر واحد بشكل معياري${\displaystyle j}$، مكتوبة على النحو التالي${\displaystyle i\ll _{\equiv }j}$، لو${\displaystyle i}$يهيمن عليها${\displaystyle j}$بالإضافة إلى عدة نسخ من${\displaystyle b}$رسميًا،${\displaystyle w_{j}+tw_{b}\leq w_{i}}$، و ${\displaystyle v_{j}+tv_{b}\geq v_{i}}$أي${\displaystyle J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1}$.

هنا، بدلاً من هدف واحد (مثل تعظيم الربح المادي من محتويات الحقيبة)، يمكن أن يكون هناك عدة أهداف. على سبيل المثال، قد تكون هناك اعتبارات بيئية أو اجتماعية بالإضافة إلى الأهداف الاقتصادية. تشمل المشكلات التي يتم تناولها بشكل متكرر تحسينات إدارة المحافظ الاستثمارية ولوجستيات النقل. ^{[ 30 ] [ 31 ]}

على سبيل المثال، لنفترض أنك تدير سفينة سياحية. عليك أن تقرر عدد الكوميديين المشهورين الذين ستوظفهم. لا تستوعب هذه السفينة أكثر من طن واحد من الركاب، ويجب ألا يتجاوز وزن الفنانين 450  كيلوغرامًا. لكل كوميدي وزن محدد، ويجذب العملاء بناءً على شهرته، ويطلب راتبًا معينًا. في هذا المثال، لديك عدة أهداف. فأنت ترغب، بالطبع، في زيادة شهرة فنانيك إلى أقصى حد مع تقليل رواتبهم إلى أدنى حد. كما ترغب أيضًا في توظيف أكبر عدد ممكن من الفنانين.

هنا، وزن محتويات حقيبة الظهر${\displaystyle i}$يُعطى بواسطة متجه ذي D بُعد${\displaystyle {\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})}$وحقيبة الظهر لها متجه سعة ذو أبعاد D${\displaystyle (W_{1},\ldots ,W_{D})}$الهدف هو تعظيم مجموع قيم العناصر الموجودة في حقيبة الظهر بحيث يكون مجموع الأوزان في كل بُعد${\displaystyle d}$لا يتجاوز${\displaystyle W_{d}}$.

تُعدّ مسألة حقيبة الظهر متعددة الأبعاد أصعب حسابيًا من مسألة حقيبة الظهر العادية؛ حتى بالنسبة لـ${\displaystyle D=2}$لا توجد مشكلة EPTAS إلا إذا كان P${\displaystyle =}$NP. ^{[ 32 ]} ومع ذلك، فقد ثبت أن الخوارزمية الواردة في ^{[ 33 ]} تحل الحالات المتفرقة بكفاءة. تُعتبر حالة مسألة حقيبة الظهر متعددة الأبعاد متفرقة إذا كانت هناك مجموعة${\displaystyle J=\{1,2,\ldots ,m\}}$ل${\displaystyle m<D}$بحيث يكون لكل عنصر من عناصر حقيبة الظهر${\displaystyle i}$،${\displaystyle \exists z>m}$بحيث${\displaystyle \forall j\in J\cup \{z\},\ w_{ij}\geq 0}$و${\displaystyle \forall y\notin J\cup \{z\},w_{iy}=0}$تحدث مثل هذه الحالات، على سبيل المثال، عند جدولة الحزم في شبكة لاسلكية تحتوي على عقد ترحيل. ^{[ 33 ]} كما تحل الخوارزمية الواردة في ^{[ 33 ]} الحالات المتفرقة من متغير الاختيار المتعدد، أي مسألة حقيبة الظهر متعددة الأبعاد ذات الاختيار المتعدد.

تُعد خوارزمية IHS (الرف ذو الارتفاع المتزايد) مثالية لمسألة حقيبة الظهر ثنائية الأبعاد (تعبئة المربعات في مربع ثنائي الأبعاد بحجم وحدة واحدة): عندما يكون هناك خمسة مربعات على الأكثر في التعبئة المثلى. ^{[ 34 ]}

هنا، توجد عدة حقائب ظهر. قد يبدو هذا تغييرًا بسيطًا، ولكنه لا يُعادل زيادة سعة الحقيبة الأصلية، إذ لكل حقيبة حدّها الخاص من السعة. يُستخدم هذا التباين في العديد من مسائل التحميل والجدولة في بحوث العمليات، وله خوارزمية تقريبية متعددة الحدود . ^{[ 35 ]} يُشبه هذا التباين مسألة تعبئة الصناديق ، ولكنه يختلف عنها في إمكانية اختيار مجموعة فرعية من العناصر، بينما في مسألة تعبئة الصناديق، يجب تعبئة جميع العناصر في صناديق مُحددة.

تُعظّم مسألة حقيبة الظهر التربيعية دالة هدف تربيعية تخضع لقيود سعة ثنائية وخطية. ^{[ 36 ]} طُرحت هذه المسألة من قِبل غالو وهامر وسيميون في عام 1980، ^{[ 37 ]} إلا أن أول معالجة لها تعود إلى ويتزغال في عام 1975. ^{[ 38 ]}

في مسألة الحقيبة الهندسية ، توجد مجموعة من المستطيلات ذات قيم مختلفة، وحقيبة مستطيلة. والهدف هو وضع أكبر قيمة ممكنة داخل الحقيبة. ^{[ 39 ]}

في مسألة حقيبة الظهر الإلكترونية ، تصل العناصر تباعًا. عند وصول أي عنصر، يجب اتخاذ قرار فوري بشأن وضعه في الحقيبة أو التخلص منه. هناك نوعان: (أ) غير قابل للإزالة - يبقى العنصر المُضاف في الحقيبة للأبد؛ (ب) قابل للإزالة - يمكن إزالة العنصر المُضاف لاحقًا لإفساح المجال لعنصر جديد.

يقدم هان وكاواسي وماكينو ^{[ 40 ]} خوارزمية عشوائية للحالة غير الموزونة وغير القابلة للإزالة. وهي خوارزمية تنافسية من الدرجة الثانية، وهو أفضل مستوى ممكن. أما بالنسبة للحالة الموزونة والقابلة للإزالة، فقد قدموا خوارزمية تنافسية من الدرجة الثانية، وأثبتوا حدًا أدنى يبلغ حوالي 1.368 للخوارزميات العشوائية، وأثبتوا أنه لا يمكن لأي خوارزمية حتمية أن تمتلك نسبة تنافسية ثابتة. وبالنسبة للحالة غير الموزونة والقابلة للإزالة، فقد قدموا خوارزمية بنسبة تنافسية 10/7، وأثبتوا حدًا أدنى يبلغ 1.25.

توجد عدة أوراق بحثية أخرى حول مشكلة حقيبة الظهر عبر الإنترنت. ^{[ 41 ] [ 42 ] [ 43 ]}