COSc 511 Homework Solutions  10/30/2014

1.Subset sums:
W (maximum weight) = 7
w1 = 2,  w2 = 2, w3 = 4

(a) Array

    0  1  2  3  4  5  6  7
--------------------------
0 | 0  0  0  0  0  0  0  0
1 | 0  0  2  2  2  2  2  2
2 | 0  0  2  2  4  4  4  4
3 | 0  0  2  2  4  4  6  6

(b) Optimal sets: {w1, w3} and {w2, w3}

(c) Optimal weight: 6


2. Travelling salesman

(a) Array

edcba | 1   	2   	3   	4   	5
----------------------------------------------
00001 | 0    |      |       |       |       |
      |
00011 |  L   |  1   |       |       |       |
      |
00101 |  L   |      |   1   |       |       |
      |
00111 |  L   |   4  |   4   |       |       |
      |
01001 |  L   |      |       |   2   |       |
      |
01011 |  L   |   6  |       |   5   |       |
      |
01101 |  L   |      |   3   |   2   |       |
      |
01111 |  L   |   6  |   6   |   5   |       |
      |
10001 |  L   |      |       |       |   2   |
      |
10011 |  L   |  7   |       |       |   6   |
      |
10101 |  L   |      |   4   |       |   3   |
      |
10111 |  L   |   7  |   8   |       |   6   |
      |
11001 |  L   |      |       |   5   |   5   |
      |
11011 |  L   |   9  |       |   9   |   8   |
      |
11101 |  L   |      |   6   |   5   |   5   |
      |
11111 |  L   |  9   |  10   |   9   |   8   |

(b) Optimum paths:

1, 5, 4, 3, 2, 1

1, 5, 3, 4, 2, 1

1, 2, 4, 3, 5, 1

1, 2, 3, 4, 5, 1

(c) Optimal weight: 10