ปัญหากระเป๋าเป็นหนึ่งในปัญหาที่มีการศึกษามากที่สุดในการหาค่าเหมาะสมเชิงการจัดเรียงโดยมีการประยุกต์ใช้ในชีวิตจริงมากมาย ด้วยเหตุนี้จึงมีการตรวจสอบกรณีพิเศษและการวางนัยทั่วไปมากมาย^{[ 1 ] [ 2 ]}

สิ่งที่เหมือนกันในทุกเวอร์ชันคือชุดของ รายการ nรายการ โดยแต่ละรายการจะมีกำไรp _jและน้ำหนักw _j ที่เกี่ยวข้อง ตัวแปรตัดสินใจแบบไบนารีx _jใช้ในการเลือกรายการ เป้าหมายคือการเลือกรายการบางส่วนที่มีกำไรรวมสูงสุด โดยต้องเป็นไปตามเงื่อนไขที่ว่าน้ำหนักรวมสูงสุดของรายการที่เลือกต้องไม่เกินWโดยทั่วไปแล้ว ค่าสัมประสิทธิ์เหล่านี้จะถูกปรับขนาดให้เป็นจำนวนเต็ม และมักจะถือว่าเป็นค่าบวกเสมอ ${\displaystyle 1\leq j\leq n}$

ปัญหาเป้สะพายหลังในรูปแบบพื้นฐานที่สุด:

เพิ่มสูงสุด${\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}$
	${\displaystyle x_{j}\in \{0,1\}}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$

รูปแบบหนึ่งที่พบได้ทั่วไปคือ แต่ละรายการสามารถถูกเลือกได้หลายครั้งปัญหาเป้สะพายหลังแบบมี ขอบเขต กำหนดขอบเขตบนu _j (ซึ่งอาจเป็นจำนวนเต็มบวกหรืออนันต์) สำหรับแต่ละรายการ j ว่า สามารถเลือก รายการ jได้กี่ครั้ง :

เพิ่มสูงสุด${\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}$
	${\displaystyle 0\leq x_{j}\leq u_{j},x_{j}}$อินทิกรัลสำหรับทุกj

ปัญหาเป้สะพายหลังแบบไม่จำกัด (บางครั้งเรียกว่าปัญหาเป้สะพายหลังจำนวนเต็ม ) ไม่ได้กำหนดขอบเขตสูงสุดสำหรับจำนวนครั้งที่สามารถหยิบสิ่งของชิ้นใดชิ้นหนึ่งได้:

เพิ่มสูงสุด${\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}$
	${\displaystyle x_{j}\geq 0,x_{j}}$อินทิกรัลสำหรับทุกj

Lueker แสดงให้เห็นว่ารูปแบบที่ไม่จำกัดเป็นNP-complete ในปี 1975 ^{[ 3 ]}ทั้งรูปแบบที่มีขอบเขตและไม่จำกัดต่างก็ยอมรับFPTAS (โดยพื้นฐานแล้วเหมือนกับที่ใช้ในปัญหาเป้สะพายหลัง 0-1)

ถ้าเราแบ่งสิ่งของออกเป็นkกลุ่ม (โดยใช้สัญลักษณ์ ) และต้องเลือกสิ่งของเพียงหนึ่งชิ้นจากแต่ละกลุ่ม เราจะได้ปัญหาเป้สะพายหลังแบบเลือกหลายรายการ : ${\displaystyle N_{i}}$

เพิ่มสูงสุด${\displaystyle \sum _{i=1}^{k}\sum _{j\in N_{i}}p_{ij}x_{ij}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{i=1}^{k}\sum _{j\in N_{i}}w_{ij}x_{ij}\leq W,}$
	${\displaystyle \sum _{j\in N_{i}}x_{ij}=1,}$	สำหรับทุกคน${\displaystyle 1\leq i\leq k}$
	${\displaystyle x_{ij}\in \{0,1\}}$	สำหรับทุกคนและทั้งหมด${\displaystyle 1\leq i\leq k}$${\displaystyle j\in N_{i}}$

หากกำไรและน้ำหนักของแต่ละรายการเท่ากัน เราจะได้ปัญหาผลรวมย่อย (บ่อยครั้งที่ปัญหาการตัดสินใจ ที่เกี่ยวข้อง จะถูกกำหนดมาให้แทน):

เพิ่มสูงสุด${\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}p_{j}x_{j}\leq W,}$
	${\displaystyle x_{j}\in \{0,1\}}$

ถ้าเรามี สิ่งของ nชิ้น และ กระเป๋าเป้ mใบ ที่มีความจุ m ใบเราจะเจอปัญหากระเป๋าเป้หลายใบ : ${\displaystyle W_{i}}$

เพิ่มสูงสุด${\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}p_{j}x_{ij}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{j}x_{ij}\leq W_{i},}$	สำหรับทุกคน${\displaystyle 1\leq i\leq m}$
	${\displaystyle \sum _{i=1}^{m}x_{ij}\leq 1,}$	สำหรับทุกคน${\displaystyle 1\leq j\leq n}$
	${\displaystyle x_{ij}\in \{0,1\}}$	สำหรับทุกคนและทั้งหมด${\displaystyle 1\leq j\leq n}$${\displaystyle 1\leq i\leq m}$

ในกรณีพิเศษของปัญหาเป้สะพายหลังหลายใบ เมื่อกำไรเท่ากับน้ำหนักและถังทุกใบมีความจุเท่ากัน เราอาจพบปัญหาผลรวมเซตย่อยหลายเซตได้

ปัญหาเป้สะพายหลังกำลังสอง :

เพิ่มสูงสุด${\displaystyle \sum _{j=1}^{n}p_{j}x_{j}+\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}p_{ij}x_{i}x_{j}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}$
	${\displaystyle x_{j}\in \{0,1\}}$	สำหรับทุกคน${\displaystyle 1\leq j\leq n}$

ปัญหาเป้สะพายหลังแบบเซตยูเนียน :

SUKP ได้รับการนิยามโดย Kellerer et al ^{[ 2 ]} (ในหน้า 423) ดังนี้:

กำหนดให้ชุดของสิ่งของและชุดของสิ่งที่เรียกว่าองค์ประกอบโดยแต่ละสิ่งของจะสอดคล้องกับเซตย่อยของเซตองค์ประกอบสิ่งของมีกำไรที่ไม่เป็นลบและองค์ประกอบมีน้ำหนักที่ไม่เป็นลบ น้ำหนักรวมของชุดของสิ่งของจะเท่ากับน้ำหนักรวมขององค์ประกอบในผลรวมของเซตองค์ประกอบที่สอดคล้องกัน เป้าหมายคือการหาเซตย่อยของสิ่งของที่มีน้ำหนักรวมไม่เกินความจุของกระเป๋าและมีกำไรสูงสุด ${\displaystyle n}$${\displaystyle N=\{1,\ldots ,n\}}$${\displaystyle m}$${\displaystyle P=\{1,\ldots ,m\}}$${\displaystyle j}$${\displaystyle P_{j}}$${\displaystyle P}$${\displaystyle j}$${\displaystyle p_{j}}$${\displaystyle j=1,\ldots ,n}$${\displaystyle i}$${\displaystyle w_{i}}$${\displaystyle i=1,\ldots ,m}$

หากมีข้อจำกัดมากกว่าหนึ่งข้อ (ตัวอย่างเช่น ทั้งข้อจำกัดด้านปริมาตรและข้อจำกัดด้านน้ำหนัก โดยที่ปริมาตรและน้ำหนักของแต่ละรายการไม่เกี่ยวข้องกัน) เราจะได้ปัญหาเป้สะพายหลังที่มีข้อจำกัดหลายข้อปัญหาเป้สะพายหลังหลายมิติหรือปัญหาเป้สะพายหลังมิติ m (หมายเหตุ "มิติ" ในที่นี้ไม่ได้หมายถึงรูปร่างของรายการใดๆ) ปัญหานี้มีหลายรูปแบบ ได้แก่ แบบ 0-1 แบบมีขอบเขต และแบบไม่มีขอบเขต โดยรูปแบบที่ไม่มีขอบเขตแสดงไว้ด้านล่าง

เพิ่มสูงสุด${\displaystyle \sum _{j=1}^{n}p_{j}x_{j}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{ij}x_{j}\leq W_{i},}$	สำหรับทุกคน${\displaystyle 1\leq i\leq m}$
	${\displaystyle x_{j}\geq 0}$จำนวนเต็ม​ ${\displaystyle x_{j}}$	สำหรับทุกคน${\displaystyle 1\leq j\leq n}$

ตัวแปร 0-1 (สำหรับค่าคงที่ใดๆ) ได้รับการพิสูจน์แล้วว่าสมบูรณ์ NPประมาณปี 1980 และยิ่งไปกว่านั้น ไม่มี FPTAS เว้นแต่ P=NP ^{[ 4 ] [ 5 ]}${\displaystyle m\geq 2}$

รูปแบบที่มีขอบเขตและไม่มีขอบเขต (สำหรับค่าคงที่ใดๆ) ก็แสดงให้เห็นถึงความยากเช่นเดียวกัน^{[ 6 ]}${\displaystyle m\geq 2}$

สำหรับค่าคงที่ใดๆปัญหาเหล่านี้ยอมรับ อัลกอริทึมเวลาพ севдо พหุนาม (คล้ายกับอัลกอริทึมสำหรับกระเป๋าเป้พื้นฐาน) และPTAS ^{[ 2 ]}${\displaystyle m\geq 2}$

ถ้ากำไรทั้งหมดเท่ากับ 1 เราจะพยายามเพิ่มจำนวนสินค้าให้มากที่สุด โดยที่ไม่เกินความจุของกระเป๋าเป้:

เพิ่มสูงสุด${\displaystyle \sum _{j=1}^{n}x_{j}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}$
	${\displaystyle x_{j}\in \{0,1\},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$

ถ้าเรามีภาชนะจำนวนหนึ่ง (ที่มีขนาดเท่ากัน) และเราต้องการบรรจุสิ่งของทั้งnชิ้นลงในภาชนะให้น้อยที่สุดเท่าที่จะเป็นไปได้ เราจะได้ปัญหาการบรรจุลงถังซึ่งจำลองโดยใช้ตัวแปรบ่งชี้ว่าภาชนะที่iกำลังถูกใช้งานอยู่ ${\displaystyle y_{i}=1\Leftrightarrow }$

ลดให้น้อยที่สุด${\displaystyle \sum _{i=1}^{n}y_{i}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{j=1}^{n}w_{j}x_{ij}\leq Wy_{i},}$	${\displaystyle \forall i\in \{1,\ldots ,n\}}$
	${\displaystyle \sum _{i=1}^{n}x_{ij}=1}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$
	${\displaystyle y_{i}\in \{0,1\}}$	${\displaystyle \forall i\in \{1,\ldots ,n\}}$
	${\displaystyle x_{ij}\in \{0,1\}}$	${\displaystyle \forall i\in \{1,\ldots ,n\}\wedge \forall j\in \{1,\ldots ,n\}}$

ปัญหาการตัดสต็อก_นั้นเหมือนกับปัญหาการบรรจุลงถังแต่เนื่องจากในทางปฏิบัติมักมีประเภทของสินค้าน้อยกว่ามาก จึงมักใช้การกำหนดรูปแบบอื่น สินค้าjจำเป็นต้อง ใช้ Bjครั้ง แต่ละ "รูปแบบ" ของสินค้าที่พอดีกับกระเป๋าเป้ใบเดียวจะมีตัวแปรx _i (มีmรูปแบบ) และรูปแบบiใช้สินค้าj b _ijครั้ง:

ลดให้น้อยที่สุด${\displaystyle \sum _{i=1}^{m}x_{i}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{i=1}^{m}b_{ij}x_{i}\geq B_{j},}$	สำหรับทุกคน${\displaystyle 1\leq j\leq n}$
	${\displaystyle x_{i}\in \{0,1,\ldots ,n\}}$	สำหรับทุกคน${\displaystyle 1\leq i\leq m}$

If, to the multiple choice knapsack problem, we add the constraint that each subset is of size n and remove the restriction on total weight, we get the assignment problem, which is also the problem of finding a maximal bipartite matching:

maximize ${\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}p_{ij}x_{ij}}$
subject to	${\displaystyle \sum _{i=1}^{n}x_{ij}=1,}$	for all ${\displaystyle 1\leq j\leq n}$
	${\displaystyle \sum _{j=1}^{n}x_{ij}=1,}$	for all ${\displaystyle 1\leq i\leq n}$
	${\displaystyle x_{ij}\in \{0,1\}}$	for all ${\displaystyle 1\leq i\leq k}$ and all ${\displaystyle j\in N_{i}}$

In the Maximum Density Knapsack variant there is an initial weight ${\displaystyle w_{0}}$, and we maximize the density of selected items which do not violate the capacity constraint: ^[7]

maximize ${\displaystyle {\frac {\sum _{j=1}^{n}x_{j}p_{j}}{w_{0}+\sum _{j=1}^{n}x_{j}w_{j}}}}$
subject to	${\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq W,}$
	${\displaystyle x_{j}\in \{0,1\},}$	${\displaystyle \forall j\in \{1,\ldots ,n\}}$

Although less common than those above, several other knapsack-like problems exist, including:

• Nested knapsack problem
• Collapsing knapsack problem
• Nonlinear knapsack problem
• Inverse-parametric knapsack problem

The last three of these are discussed in Kellerer et al's reference work, Knapsack Problems.^[2]