算法概论作业6.17 6.18 6.23 6.26

算法概论作业

6.17

给定数量无限的面值分别为x1,x2,…,xn的硬币，我们希望将价格v兑换成零钱。也即，我们希望找出一堆总价值恰好为v的硬币。这有时候是不可能的：例如，如果硬币只有5和10两种面值，则我们可以兑换15却不能兑换12.请给出一个针对如下问题的O(nv)的动态规划算法：
输入：x1,x2,…xn;v
问题：能否用面值分别为x1,x2..,xn的硬币兑换价格v？

DP方程：

bool canChange(int *x,int n,int v)
{
    bool h[v];
    int j;
    h[0]=true;
    for(j=1;j<=v;j++)
        h[j]=false;//initialization
    for(j=1;j<=v;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(j==x[i])
                h[j]=true;
            else if(j>x[i])
                h[j]=h[j] || h[j-x[i]];
        }
    }
    return h[v];
}

6.18

考虑以上零钱兑换问题的一个变形：您有面值x1,x2…xn的硬币，希望兑换的价格为v，但是每种面值的硬币最多只能使用一次。举例来说，如果硬币面值为1,5,10,20，则可兑换的价包括1+15=16,1+10+20=31,但是无法兑换40（因为20不能用2次）。请说明如何在O（nv）时间内解决该问题。

DP方程:
$h(i,j)= h(i-1,j-x[i]) || h(i-1,j)$

代码：

For(i=0;i<=n;i++)
    H(I,0)=0;
For(j=0;j<=v;j++)
    H(0,j)=0;
For(i=1;i<=n;i++)
    For(j=1;j<=v;j++)
        H(i,j)=h(i-1,j-x[i]) || h(i-1,j)

6.23

一个生产系统共包含n个顺序执行的阶段。每个阶段i（1<=i<=n）由对应的机器Mi执行。Mi可靠工作的概率为ri(失效的概率为1-ri)。因此，如果我们在每个阶段都只使用一台机器，整个系统可靠工作的概率将为r1*r2…rn。为了有所改进，我们引入机器的冗余，即对每台机器Mi都建立mi个副本。Mi的所有mi个副本同时失效的概率为（1-ri）^mi，这意味着第i阶段工作顺利完成的概率为1-（1-ri）^mi，从而整个系统的可靠性提高到了∏(1-(1-ri)^mi)。设机器Mi的成本为ci，购买机器的总预算为B（假设B和ci都是正整数）
    给定概率r1,r2…rn,成本c1,c2…cn和预算B，请给出在预算范围内进行冗余配置的策略(m1,m2…mn),以最大限度的保证系统的可行性。

思路：

假设h(I,j)为前i个阶段预算为j的最大正常运行概率。
前i-1个阶段可能情况为h(i-1,j-mc[i])*(1-(1-ri)^m),m>=1,
h(I,j)取其中的最大一个，并且由于前i-1个阶段每个机器至少要1个，
所以m*c[i]<=j-(c[1]+c[2]+…+c[i-1]),
令s[i]=c[1]+c[2]+…+c[i],
那么m*c[i]<=j-s[i-1]。

DP方程：

$h(i,j)$ = 1, $i=0 | j=0$
$h(i,j)$ = $Max(H(i-1,j-mc[i])*(1-(1-ri)^m))$ $(m>=1,m*c[i]<=j-s[i-1]), others$

代码：

IntI,j;
For(i=0;i<=n;i++)
    H(I,0)=1;
For(j=0;j<=B;j++)
    H(0,j)=1;
For(i=1;i<=n;i++)
    For(j=1;j<=B;j++)
        H(I,j)=0;
For(i=1;i<=n;i++)
    For(j=1;j<=B;j++)
        Int m=1;
        While(m*c[i]<=j-s[i])
            If(h(i-1,j-m*c[i])*(1-(1-ri)^m)>h(I,j))
                H(I,j)=h(i-1,j-m*c[i])*(1-(1-ri)^m);
Return h(n,B);

6.26

序列对齐。新的基因被发现后，为了了解其功能，一个常用的方法是查找已知基因中与之相似的基因。两个基因之间的相似度是由他们可以相互对齐的程度决定的。为了对他进行量化，考虑基于字母表M={A,C,G,T}定义的字符串。设两个基因（字符串）分别为x=ATGCC,y=TACGCA。X和y的一个对齐是指将它们都横向书写，然后将其中相同的字符进行匹配的方式，例如：
    -   A   T   -   G   C   C
    T   A   -   C   G   C   A
其中：“-”表示一个空隙；串中所有字符必须保持原有的顺序，且每行必须包含至少一个字符串的某个字符。对齐的分值基于一个（M+1）*（M+1）的评分矩阵定义，其中包含特定的行和列对应于空隙的情况。举例来说，此前列举的对齐方式分值如下：
    O(-,T),O(A,A),O(T,-),O(-,C),O(G,G),O(C,C),o(C,A)
请给出一个动态规划算法，以两个字符串x[1…n],y[1…m]以及评分矩阵为O为输入，返回分值最高的对齐。要求运行时间为O（mn）。

DP方程：
$h(I,j)=$ $max${ $h(i-1,j)+O(x[i],-)$, $H(I,j-1)+O(-,y[j])$,$H(i-1,j-1)+O(x[i-1],y[j-1])$ }

代码：

Int i,j;
For(i=0;i<=n;i++)
    For(j=0;j<=m;j++)
        H(I,j)=0;
For(i=1;i<=n;i++)
    For(j=1;j<=m;j++)
    {   H1=h(i-1,j)+O(x[i],-);
        H2=h(I,j-1)+O(-,y[j]);
        H3=h(i-1,j-1)+O(x[i],y[j]);
        If(h1>h(I,j))
            H(I,j)=h1;
        If(h2>h(I,j))
            H(I,j)=h2;
        If(h3>h(I,j))
            H(I,j)=h3;}
Return h(n,m)