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

ปัญหาถุงกระสอบ (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