11-1, 11-3, 11-5, 13-1, 13-2, 13-3

11-1

(a) W=[3,2,1,2]如果我们按照顺序装箱,K =4，得到的应该是{3},{2,1},{2},需要3辆车. 但是最优解为{3,1}，{2,2}, 需要2辆车就足够了。

(b)假设使用这个算法得到的结果是需要调度2q+1辆车（我们先验证奇数的情况）。

把他们排列后两两一组，除了最后一组，每组的weight $w2_i$满足 $k<w2_i\le 2k$, 最后一辆车的weigh满足 $0<w \le k$, 因此求和得到 $qk <\sum_{n=1}^N w_i <(2q+1)*k \quad (1)$, 因为最优解OPT一定满足 $OPT>\frac{\sum_{n=1}^N w_i}{k}\quad (2)$, 结合（1）（2）得到

$$ OPT>q \\ \therefore OPT\ge q+1 \\ \therefore 2*OPT>2q+1 $$

当我们需要调度2q辆车，分组后，我们同样可以得到

$$ q*k <\sum_{n=1}^N w_i <(2q)*k \quad (3)\\OPT>\frac{\sum_{n=1}^N w_i}{k}\quad (4)\\ 2OPT > 2q $$

证毕。

11-3

(a)A={5,4,3} B=8, OPT={4,3}, 使用这个算法结果为{5}

(b)

int sum=0;
for(int i = 0;i < n; i++){
	if(w[i] > B)continue;
	if(sum+w[i] <= B) sum+= w[i];
	else{
		// w[i] or sum must greater than B/2, we just choose the larger one
		return max(sum, w[i]);
	}
}

遍历每一个权重，当sum+w[i]没有超过的时候就加入sum, 当超过了，我们可以发现一定有 sum 或者 w[i] > B /2 , 于是我们返回较大的值就可以了。这个只有一层循环，复杂度为O(n).

11-5