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

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

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

การแก้ปัญหา[แก้]

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

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

 1 def knapSack(W, wt, val, n):
 2     K = [[0 for x in range(W+1)] for x in range(n+1)]
 3  
 4     # Build table K[][] in bottom up manner
 5     for i in range(n+1):
 6         for w in range(W+1):
 7             if i==0 or w==0:
 8                 K[i][w] = 0
 9             elif wt[i-1] <= w:
10                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
11             else:
12                 K[i][w] = K[i-1][w]
13  
14     return K[n][W]

อ้างอิง[แก้]

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