 |
กลับมาอธิบายอีกซักหน่อย
คือ มันเป็นแบบนี้
.ให้ i คือสิ่งของแต่ละชิ้น
ผมให้ w_i เป็นน้ำหนักของสิ่งของแต่ละชิ้น
ให้ v_i เป็นมูลค่าของสิ่งของแต่ละชิ้น
ให้ W เป็นข้อจำกัดน้ำหนักสูงสุดที่จะพาไปได้
ผมให้ P(i,k) เป็นคำตอบของปัญหานี้ ซึ่งเราต้องการ Maximize (ผมรวมของมูลค่าต่อน้ำหนัก) ให้ใกล้เคียง W ที่สุดเท่าที่จะเป็นไปได้
นิยาม V( i, w ) เป็นน้ำหนักของสิ่งที่อยู่ในถุงจะได้ว่า
V(i,w) = max( V(i ,W-w_i) + v_i , V( i-1, w) )
จากสมการ V(i,w) จะเห็นการทับซ้อนของปัญหาย่อย ** ใช้ DP เพื่อแก่ปัญหา
ผมว่าที่นี่คงมีคนแพ้สมการเยอะ
V(i,w) = max( V(i ,w-w_i) + v_i , V( i-1, w) )
อธิบายคือ เราต้องเลือกที่จะหยิบหรือไม่หยิบ โดย ดูจากมุลค่าว่าหยิบไปแล้วคุมกับน้ำหนักใหม?
โดยเงื่อใขเริ่มต้นคือ
V(0,w)= 0
V(w,0) =0
ฉะนี้แล้ว จึงใช้ DP
| จากคุณ |
:
นฤมลประการ  
|
| เขียนเมื่อ |
:
24 ส.ค. 55 20:43:59
|
|
|
|
|
อยากทราบทฤษฎี หรืออะไรก็ได้ที่เกี่ยวกับโปรแกรมมิ่ง เทคโนโลยี
