有一批集装箱要装上一艘载重量为\(C\)的轮船，其中集装箱\(i\)的重量为\(w_i\)。最优装载问题要求确定，在装载体积不受限制的情况下，应该如何装载才能将尽可能多的集装箱装上轮船。该问题形式化描述为：

\[\begin{align} &max\quad \sum\limits_{i=1}^nx_i\\\\ &s.t.\quad \begin{cases} \sum\limits_{i=1}^nw_ix_i \leq C \\\\ x_i \in\lbrace0,1\rbrace,1 \leq i \leq n \end{cases} (*) \end{align}\]

对于这道题目，直觉上的想法就是从集装箱重量小的开始装。因为我们的目标函数是可装船的集装箱的数目，而非重量。恰巧，这正是贪婪的想法。

最优子结构性质的证明如下：

设\(x_1,x_2,\cdots,x_n\)是最优装载问题的一个满足最优贪心选择性质的最优解，则容易知道，\(x_1=1,(x_2,x_3,\cdots,x_n)\)是轮船载重量为\(C-w_1\)且待装船集装箱为\({2,3,\cdots,n}\)时相应最优装载问题的一个最优解。

最优子结构性质是可以利用贪心和动态规划思想解决的题目都具有的性质。对于几乎所有问题都具有相同的证明思路而且相对容易。只要证明原问题的最优解包含子问题的最优解就可以搞定。

来看看贪心选择性质的证明(是对王晓东老师教材证明的补充和理解)：

设集装箱已经依其重量从小到大排序，\((x_1,x_2,\cdots,x_n)\)是最优装载问题的一个最优解。设：

\[\begin{align} k = min\lbrace i|x_i=1\rbrace\quad 1 \leq i \leq n \end{align}\]

容易知道，如果给定的最优装载问题有解，则\(1 \leq k \leq n\)。\(x_i=1\)表示第\(i\)个集装箱装船，则\(k\)的含义是第一个装船的集装箱的序号(有序排列下)。这样的话，在问题有解的情况下，必然有集装箱要装船，也就有了\(k\)的取值范围。

当\(k=1\)的时候，\((x_1,x_2,\cdots,x_n)\)是一个满足贪心选择性质的最优解。原因是这是一个按照从小到大排列的序列,\(k=1\)表示序号为1(重量最小)的集装箱装船，显而易见的结论。

当某个最优解满足第一个装船的集装箱的重量不是最小的时候，如果能够证明从重量最小的集装箱(序号为1)装船 也是一个最优解，那么便可以证明贪心选择性质。因为从贪心选择的定义上，试图一步步贪心选择达到最终全局最优（虽然贪心不一定会得到全局最优）。我们就是要证明可以回到最初选择（选择重量最小，序号为1的集装箱）进而一步步达到最优解。

为了证明这个想法，先要构造一个一般情况，也就是最优解满足第一个装船的集装箱的重量不是最小的情况。

当\(k>1\)的时候，取\(y_1=1;y_k=0;y_i=x_i,1 \le i \leq n,i\not=k\)

\(k>1\)就是一般情况，对应装船策略记为X。此时，序号为\(1至(k-1)\)的集装箱没有装船。此时假设的另外一种装船策略就是用\(y_i\)来表示的序列，记为Y，后续会证明这个序列是可行解，同时也是最优解。观察这个策略的特征：

\(y_1=1\)表示第一个重量最轻的集装箱装船。\(y_k=0\)表示策略X中第一个装船的集装箱在策略Y中不装船。\(y_i=x_i,1 \le i \leq n,i\not=k\) 表示除了上述两个集装箱状态变动外，对于其余集装箱，策略Y和策略X相同。上图：

图片

策略X和策略Y的装船对比图，第一行为策略X，第\(k\)个集装箱装船；第二行为策略Y，第1个集装箱装船，第\(k\)个集装箱不装船，其余集装箱装船状态同策略X。

构造策略X和Y之后，只要证明Y也是最优解这个问题就算搞定，证明最优解，从可行解开始，也就是新的策略Y能够满足重量限制。

\[\sum\limits_{i=1}^nw_iy_i=w_1-w_k+\sum\limits_{i=k}^nw_ix_i \leq \sum\limits_{i=k}^nw_ix_i \leq C\]

观察上式，对策略X，第\(k\)个集装箱装船，而在策略Y中没有装船。此外，由于集装箱是按照重量大小进行排序，则\(w_1 \leq w_k\)。

上式两边同时加上\(\sum\limits_{i=1}^{k-1}w_ix_i\),就是王晓东老师教材上的表达了。 为什么？回到对\(k\)的定义，序号为\(k\)的集装箱是第一个装船的集装箱，则第\(k\)个集装箱前边的集装箱都没有装船，也就是\(\sum\limits_{i=1}^{k-1}w_ix_i=0\)，故有：

\[\sum\limits_{i=1}^nw_iy_i=w_1-w_k+\sum\limits_{i=1}^nw_ix_i \leq \sum\limits_{i=1}^nw_ix_i \leq C\]

由于策略X和策略Y只是交换了第\(1\)和第\(k\)个集装箱的装船状态，故两种策略装船的集装箱的数目相同，也就是策略Y也是一个最优策略，得到的装船序列也是一个最优解。即：

\[\sum\limits_{i=1}^ny_i = \sum\limits_{i=1}^nx_i\]

额，说了这么多，个人认为亮点只有一个，就是给定策略X，策略Y的构造方式。当然如何想到用这种方式去证明贪心策略，似乎也不是那么显而易见。