2011-8 第1問 (1-2)

探索木
* P0
** P1 : x1 = 1
*** P2 : x2 = 1, x3 = 0
**** P3 : x4 = 1, x5 = 0 ダメ
**** P4 : x4 = 0
*** P5 : x2 = 0
**** P6 : x3 = 1, x4 = 0, x5 = 0 ダメ
**** P7 : x3 = 0 ダメ
**P8 : x1 = 0 ダメ

P0 : 問題 A1
>下界 : 45 (1, 1, 0, 1, 0) :: 暫定値
>上界 : 51 (1, 1, 1/2, 0, 0)

P1 : x1 = 1
>下界 : 45 (1, 1, 0, 1, 0)
>上界 : 51 (1, 1, 1/2, 0, 0)

P2 : x1 = 1, x2 = 1, x3 = 0
>下界 : 45 (1, 1, 0, 1, 0)
>上界 : 49 (1, 1, 0, 1, 1/3)

P3 : x1 = 1, x2 = 1, x3 = 0, x4 = 1, x5 = 0
>下界 : 44 (1, 1, 0, 1, 0)
>上界 : 44 (1, 1, 0, 1, 0) < 暫定値 45

P4 : x1 = 1, x2 = 1, x3 = 0, x4 = 0
>下界 : 48 (1, 1, 0, 0, 1) :: 暫定値
>上界 : 48 (1, 1, 0, 0, 1)

P5 : x1 = 1, x2 = 0
>下界 : 44 (1, 0, 1, 0, 0)
>上界 : 49.5 (1, 0, 1, 1/2, 0)

P6 : x1 = 1, x2 = 0, x3 = 1, x4 = 0, x5 = 0
>下界 : 44 (1, 0, 1, 0, 0)
>上界 : 44 (1, 0, 1, 0, 0) < 暫定値 48

P7 : x1 = 1, x2 = 0, x3 = 0
>下界 : 35 (1, 0, 0, 1, 1)
>上界 : 35 (1, 0, 0, 1, 1) < 暫定値 48

P8 : x1 = 0
>下界 : 43 (0, 1, 0, 1, 1)
>上界 : 47 (0, 1, 5/6, 0, 0) < 暫定値 48

以上より、
x1 = 1, x2 = 1, x3 = 0, x4 = 0, x5 = 1のとき最大合計価値 48