ปัญหาถุงกระสอบ

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

ตัวอย่างของปัญหากระเป๋าเป้สะพายหลัง(constraint): ควรเลือกกล่องใดเพื่อเพิ่มจำนวนเงินในขณะที่ยังคงรักษาน้ำหนักโดยรวมไว้ไม่เกินหรือเท่ากับ 15 กิโลกรัม ปัญหาข้อจำกัด หลายอย่างอาจพิจารณาทั้งน้ำหนักและปริมาตรของกล่อง (วิธีแก้: ถ้าให้ใส่กล่องจำนวนเท่าใดก็ได้ ให้ใช้กล่องสี่เหลี่ยมสีเหลือง 3 กล่องและกล่องสีเทา 3 กล่อง แต่ถ้าใส่ได้อย่างละอันก็ให้ใส่ทุกอันนอกจากกล่องสีเขียว)

การแก้ปัญหา

- วิธีที่ตรงไปตรงมาที่สุดคือการไล่ทดลอง หยิบ/ไม่หยิบ ของแต่ละชิ้น แล้วหามูลค่ารวมที่มากที่สุดโดยน้ำหนักรวมไม่เกินที่กำหนด

- การใช้ Dynamic programming เข้ามาเพื่อหลีกเลี่ยงการทำซ้ำๆ โดยสร้าง array K[][]

def knapSack(W, wt, val, n):  K = [[0 for x in range(W+1)] for x in range(n+1)]   # Build table K[][] in bottom up manner  for i in range(n+1):  for w in range(W+1):  if i==0 or w==0:   K[i][w] = 0  elif wt[i-1] <= w:   K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])  else:   K[i][w] = K[i-1][w]   return K[n][W] 

อ้างอิง

detohm. 0-1-knapsack-problem-. FINOMENA. 14 May 2018