贪婪算法（合理分配，最大积）

算法（合理分配，最大积）"/>

贪婪算法（合理分配，最大积）

Assignment 3

Q1:

代码:

把猴子和香蕉按照从左到右的顺序编号，当每个猴子拿到对应顺序的香蕉的时候所有猴子拿完香蕉花费的时间最少。比如说左起第一个猴子应该拿左起的第一根香蕉，以此类推。

def assignBananasToMonkeys(bananas,monkeys):bananas.sort()monkeys.sort()res = 0for i in range(len(bananas)):res = max(res,abs(bananas[i]-monkeys[i]))return res

贪婪选择策略:

每个猴子选择其对应位置的香蕉，举例，左起第一个猴子应该拿左起的第一根香蕉

最优子结构:

第i个猴子拿第i根香蕉

算法正确性:

1. 对于所有的分配方式，第i个猴子要么拿到第i根香蕉或者没有，我们暂时把第i个猴子拿第j根香蕉这种猴子香蕉对叫做乱序对，那么，我们不失一般性的把所有乱序对拿出来，按照从左到右的顺序把猴子和香蕉排序一次，得到monkeys和bananas两个序列。
2. 如果我们按照第i个猴子拿了第j根香蕉，第j个猴子拿了第k根香蕉的方式进行下去，最后必定会存在第m个猴子拿了第i根香蕉，也就是说，本质上来说，这些乱序对构成了多个长度不同的环。例子：第一个猴子拿第二根香蕉，第二个猴子拿第一根香蕉，构成一个长度为2的环。
3. 因为这些乱序对构成了多个环，不失一般性，我们暂时就假设前i个猴子乱序和前i根香蕉乱序，构成长度为i的环，并且这个环不能再拆出新的子环。我们只需要证明对长度为i的环，其花费的最大时间大于按照顺序拿即可。
4. 对于所有的这些环，我们要遵循两个前提。第一个是，每个猴子必定不应该去拿距离大于它拿对应序号的香蕉的距离的香蕉，这样的拿法是没有意义的，必定达不到最优解。第二个点，乱序的根本原因是因为多步决策下第k个猴子拿了离他更近的香蕉，而这根香蕉不是第k根香蕉，否则满足第一个前提下一部分猴子贪婪，一部分不贪婪，那么该环一定可以继续拆分。这种情况下该环必定是第i个猴子取第一根香蕉，而这种情况下，此时其需要走的路径是最左最右两个端点连起的整条直线的长度，大于按照顺序取。得证
5. 那么为什么长度为i的环必定是最后一个猴子拿第i根香蕉，考虑第一个猴子为什么不拿第一根香蕉，必定是因为存在另一根香蕉离他更近，那么此时对于所有的其他猴子来说，都不愿意跑更远的路去拿第一根香蕉，多步决策贪婪之后必定是第i个猴子拿了第一根香蕉，我们假设不是第i个猴子而是第k个猴子拿的第一根香蕉，那么此时第k个猴子没有遵循贪婪的原则，那么此时就构成了一个长度小于i的环，可以拆分出去，和我们的假设矛盾，因此必定是最后一个猴子拿的第一根香蕉。
6. 针对3中存在的所有构成环的乱序对，最终，所有乱序对中的猴子最终导致它们整体拿完香蕉所需要的时间要大于它们按照顺序拿香蕉的所需要的时间，极端情况比如猴子位置重复，香蕉位置重复等，会出现等于的情况。
7. 因此按照顺序拿香蕉所花费的时间必定小于或者等于所有其他不按照顺序拿香蕉的方式所花的时间。算法正确性得证。

算法复杂度:O(nlogn):

两次排序加一次数组遍历

O(2nlogn+n) = O(nlogn) 

Q2:

代码:

要使得绳子拆分之后积最大，其因子必定是2或者3

def ropeBreak(n):if n==2:return 1if n==3:return 2if n==4:return 4num = n//3remain = n%3if remain==1:return 3**(num-1)*(remain+3)elif remain==0:return 3**(num)else:return 3**(num)*2

贪婪选择策略:

将绳子尽可能拆分成长度为3的部分，并且不能使得剩余长度为1的情况出现

最优子结构:

如果从dp的角度去思考，对于数n，拆分成两部分的话，其最大值必定是n/2*n/2或者n//2*(n//2+1)，对于n/2长度的部分继续做拆分，直到其长度不能拆分使得其积大于其本身为止，即2或者3，此时其最优子结构为：

长度为n的绳子，其拆分之后积的最大值为dp[n]

其中dp[0:4] = [0,1,2,3,4]

算法正确性:

对于数字num>=4，我们总可以拆分成(num-2)*num>=num

所以所有大于等于4的因子都可以被拆分，而又因为3*3大于2*2*2，所以每三个为2的因子可以被替换成两个3的因子，因子为1没有意义，因此最后结果中，因子必定为2或者3，同时2的个数必定不超过2.

算法复杂度:O(logn)  n为绳长

这里唯一耗时间的运算就是幂运算，也就是3**(n//3)，复杂度为O(n//3)，如果我们用快速幂算法的话，复杂度可以变成O(log(n//3)),也就是O(logn)