在此处输入标题
在此输入正文
EX1:1234567891011121314151617import randomdef darts(n): k = 0 for i in range(n): x = random.uniform(0, 1) y = x if
...
算法概论作业6.17 6.18 6.23 6.26
发表于
|
分类于
算法概论作业
#6.17123给定数量无限的面值分别为x1,x2,…,xn的硬币，我们希望将价格v兑换成零钱。也即，我们希望找出一堆总价值恰好为v的硬币。这有时候是不可能的：例如，如果硬币只有5和10两种面值，则我们可以兑换15却不能兑换12.请给出一个针对如下问题的O(nv)的动态规划算法：输入：x1,x2,
...
算法概论作业6.16 6.19 6.21 6.14
发表于
|
分类于
算法概论作业
#6.161本题目的起始顶点（ home）可以访问多次，而且不必访问所有的顶点。以 B(S j , )来表示在 garage sale 集为 S ，结束位置为 j 的子问题上的最大收益值。注意 j 的前导顶点既可能是某个 garage sale，也可能是 home，于是有Dp方程：
DP方程：
#
...
算法概论作业5.26 5.28 5.33
发表于
|
分类于
算法概论作业
#5.2612以下是程序自动分析中的一个问题。对于一组变量x1,x2,…,xn,给定一些形如“xi=xj”的等式约束和形如“xi≠xj”的不等式约束这些约束能否同时满足？例如，如下一组约束：x1=x2,x2=x3,x3=x4,x1≠x4，是无法同时满足的，请给出一个有效的算法，判断关于n个变量的m
...
算法概论作业5.21 5.22 5.32
发表于
|
分类于
算法概论作业
#5.22a) 设这个环的顶点集为 C ，最大权边为 e u v ( , ) 。设在某一时刻， C 被 cut 成两个部分s s 1 2 , ，其中 s1包含 u ，而 s2 包括 v 。因 C 是一个环，所以连结 s s 1 2 , 的边至少有两条，其中至少有一条不为 e 的边 e’，其权不大于
...