解 0-1背包問題
範例：有個背包可承受10kg的重量，請依下列項目選出最有價值的組合放入背包中
i = 物品1、物品2、物品3、物品4
w = 重量
p = 價值
_________________________________________________________________________________
○ 動態演算法的解法：
1. 先將問題分成4個部分 (物品1、物品2、物品3、物品4)
2. 依序決定是否要將物品收在背包中且不超過負重量
3. 圓圈內的1、0分別代表有、無放進背包中的記號
※ 0、1 表示第一項物品取值情況
※ 00、01 表示第二項物品取值情況，00→ 第1個0為第1項物品沒有拿，第2個0為第2項物品沒有拿
01→ 第1個0為第1項物品沒有拿，第2個1為第2項物品有拿
※ 000、001 表示第二項物品取值情況，000→ 第1個0為第1項物品沒有拿，第2個0為第2項物品沒有拿
第3個0為第3項物品沒有拿
001→ 第1個0為第1項物品沒有拿，第2個0為第2項物品沒有拿
第3個1為第3項物品有拿
以此類推......
Tips： x1= 1，x1用來表示 物品1；後面的1則為有拿物品
x1= 0，x1用來表示 物品1；後面的0則為沒拿物品
線上數值代表物品價值
以最佳解法為例：
先決定是否要將 物品1放進背包，要放的話往圓圈1的方向走，不放的話往圓圈0的方向走
起點為圓圈S
● 1. 決定不放物品1，往圓圈0的方向走
● 2. 放入物品2，價值 $30，背包重4kg，走到圓圈01的位置
● 3. 再放入物品3，總價值 $50，背包總重9kg，走到圓圈011的位置
● 4. 背包總重9kg且已經沒有低於1kg的東西可以裝，於是走到圓圈0110的位置
● 5. 已無任何選擇所以走到圓圈T，結束。
所求得的最佳解為：
S→01→011→0110→T
背包總重：9KG
價值： $50
沒有留言:
張貼留言