6-1, 6-2, 6-3, 6-11, 6-12, 6-13

6-1

(a) 8-9-7 这个算法得到的是{9} ， 但是答案应该是{8,7} 8+7=15>9

(b) 8-3-2-19 这个算法得到的是{3,19} 3+19=21, 但是答案应该是{ 8,19} 8+19>3+10

(c)

定义Max[i], 是指可以选择前i+1个node来得到结果的值

w[i] 为第i个node的weight

思路：Bottom up的DP算法

每次在path的后面加一个节点i，那最大independent set里面可能有的值是（1）这个节点没有加入，不更新。是加入这个节点前(i-1)的最大independent set值 (Max[i-1])（2）这个节点加入，由定义，于是不可能用相邻的i-1 个节点，所以是Max[i-2]+ w[i]

取这两个值记录到Max[i]里面。当到最后一个值i=length-1的时候，Max[length-1]就是所求的值

时间复杂度分析：因为之前的状态（Max[])都被记录下来了，所以对于每次循环，都是O(1)的，因此时间复杂度是O(n)

int calWeight(int length, int w[]){
	int Max[length]
	Max[0]= w[0];
	Max[1]= max(w[0],w[1]);
	for( int i=2;i<length;i++){
		Max[i]=max(Max[i-1], Max[i-2]+wi);
	}
	return Max[n-1];
}

动态规划只要用递推式就可以了

6-2

(a)这个算法的问题在并没有考虑所有的H