算法3.电路布线和0-1背包问题

港控/mmm° 2022-07-14 13:42 126阅读 0赞

1.  ![这里写图片描述][SouthEast]  
    (1) 算法设计思路  
    ① 当i=1，MNS（0j）=nets（0\#（j）），如果j<\#(1,size(j)=0,否则size(1，j)=1  
    ② 当i>1，如果j<\#(i)，nets(i,\#(j))=nets(i-1,\#(j)),size(i,j)=size(i-1,j)。否则，size(i,j)=MAX\{size(i-1)，size(i-1,\#(i)-1)+1\}

(2) 算法实现的伪代码  
计算最优值的算法functionA(int n, int\[\] A,int\[\]\[\] size)  
输入：n个接线柱，下端接线柱A\[\]，备忘录size\[\]\[\].  
输出：  
s1: for int j=1 to A\[0 size\[\[j\]=0;end for  
s2: for int j=A\[1\] to n,size\[1\]\[j\]=1;end for  
s3: for int i=2 to n  
s4: for int j=1 to A\[i\]-1, size\[i\]\[j\]=size\[i-1\]\[j\];end for  
s5: for int j=A\[i\] to n,size\[i\]\[j\]=max(size\[i-1\]\[j\],size\[i-1\]\[A\[i\]-1\]+1);end for  
s6: end for  
s7: size\[n\]\[n\]=max(size\[n-1\]\[n\],size\[n-1\]\[A\[n\]-1\]+1);  
(1) 实验代码

public class 电路布线 {
            static void MNS(int n,int[] A,int[][] size){
                for (int j=1;j<A[1];j++)//当i=1的时候，所有j<A[1]进行赋值为0
                    size[1][j]=0;
                for (int j=A[1];j<=n;j++)//当i=1的时候，所有j>=A[1]进行赋值为1
                    size[1][j]=1;
                for (int i=2;i<=n;i++){
       //当i>1时，
                    //如果j<A[i],（i，A[i]）不属于N（i，j），size[i][j]=size[i-1][j]
                    for (int j=0;j<A[i];j++)
                        size[i][j]=size[i-1][j];
                    //若j>A[i],如果(i,A[i])属于N（i，j），则有size(i,j)=size[i-1][A[i]-1]
                    //反正则和j<A[i]一样，结果取这两种情况最大值
                    for (int j=A[i];j<n;j++)
                        size[i][j]=Math.max(size[i-1][j], size[i-1][A[i]-1]+1);
                }
                //将所有的数据记录起来
                size[n][n]=Math.max(size[n-1][n], size[n-1][A[n]-1]+1);
            }
    
            static int Track(int n,int[] A,int[][] size,int[] net){
                int j=n;
                int m=0;
                for (int i=n;i>1;i--)
                    if (size[i][j]!=size[i-1][j]){
                        net[m++]=i;
                        j=A[i]-1;
                    }
                if (j>=A[1])
                    net[m++]=1;
                return m;
            }
            public static void main(String[] args) {
                int n=10;
                int[] A={
       0,8,7,4,2,5,1,9,2,10,6};
                int[][] size=new int[11][11];
                int[] net = new int[11];
                MNS(n, A, size);
                int m=Track(n, A, size,net);
                System.out.println(m);
            }
        }

O(n)=n^2

(3) 体会  
在分析的时候，一般都是从特殊情况考虑的，然后再从特殊值到一般值。一开始的时候，比较难想到j>∏（i）的时候分为2种情况。后来通过复习一下该算法才勉强记得出来和写出来。一般来说电路布线可以分为属于最大相交子集和不属于相交子集，通过分析就可以很快的得到思路和将伪代码写出来

1.  ![这里写图片描述][SouthEast 1]
2.    
    (1) 算法设计思路  
    n种物品，物品i的重量是Wi，价值为Vi，背包容量为C，存在x（1,2,3,4,5….n）属于\{0,1\}。  
    设最优子问题的最优值为m(i,j)，即背包容量为j，可以选物品为i,i+1…n。  
    `当i=n时：如果j<Wi,m(i,j)=m（n，j）=0. 如果j>Wi,m(i,j)=m(n,j)=Vn. 当0<i<n时，如果j<Wi,,m(i,j)=m(i+1,j) 如果j>Wi , m(i,j)=Vi+m(i+1,j-Wi) m(i,j)=(m+1,j) m(i,j)=max{m(i+1,j-Wi)+Vi,m(i+1,j)}`  
    (2) 算法实现的伪代码

A. 计算最优值的算法functionA(int n,int c , int\[\]\[\] m,int w\[\],int v\[\])  
输入：n种物品，物品的重量w\[\],价值v\[\],背包容量C，最优子问题的最优值m\[\]\[\]  
输出：m\[n\]\[c\]  
s1: int jmax=min(w\[n\]-1,c)  
s2: for (int j=0 to jmax)m\[n\]\[j\]=0; end for  
s3: for (int j=w\[n\] to c) m\[n\]\[j\]=v\[n\]; end for  
s4: for (inti =n-1 to 2)  
s5: jmax=min(w\[n\]-1,c);  
s6: for (int j=0 to jmax) m\[i\]\[j\]=m\[i+1\]\[j\];  
s7: for (int j= jmax to c) m\[i\]\[j\]=max\{m\[i+1\]\[j-w\[i\]\]+v\[i\] , m\[i+1\]\[j\] \}  
s8: end for  
s9: m\[1\]\[c\]=m\[2\]\[c\];  
s10: if (c>=w\[1\]) m\[1\]\[c\]=max(m\[1\]\[c\],m\[2\]\[c-w\[1\]\]+v\[1\]);  
B. 构造最优解的算法functionB(int\[\]\[\] m, int\[\] w,int c,int n,int\[\] x)  
输入：子问题最优值m\[\]\[\]，物品重量w\[\]，背包容量C，物品个数N，存储是否放入背包x\[\]  
输出：x\[\]  
s1: for (inti =1 to n-1)  
s2: if (m\[i\]\[c\]==m\[i+1\]\[c\]) x\[i\]=0;  
s3: else \{x\[i\]=1,c-=w\[i\]\}  
s4: end for  
s5: x\[n\]=(m\[n\]\[c\])?1:0

(1) 实验代码

public class 背包01 {
            /* * n种物品，物品i的重量是Wi，价值为Vi，背包容量为C，存在x（1,2,3,4,5….n）属于{0,1}。 设最优子问题的最优值为m(i,j)，即背包容量为j，可以选物品为i,i+1…n。 ① 当i=n时：如果j<Wi,m(i,j)=m（n，j）=0. 如果j>Wi,m(i,j)=m(n,j)=Vn. ② 当0<i<n时，如果j<Wi,,m(i,j)=m(i+1,j) 如果j>Wi , m(i,j)=Vi+m(i+1,j-Wi) m(i,j)=(m+1,j) m(i,j)=max{m(i+1,j-Wi)+Vi,m(i+1,j)} */
            static void funA(int n,int c,int[][] m,int[] w,int[] v){
                int jmax=Math.min(w[n]-1, c);//获取最小值
                for (int j=0;j<=jmax;j++)//j<Wi,m(i,j)=m（n，j）=0
                    m[n][j]=0;
                for (int j=w[n];j<=c;j++)//j>Wi,m(i,j)=m(n,j)=Vn.
                    m[n][j]=v[n];
                for (int i=n-1;i>1;i--){
                    jmax=Math.min(w[i]-1,c);
                    for (int j=0;j<=jmax;j++)//j<Wi,,m(i,j)=m(i+1,j)
                        m[i][j]=m[i+1][j];
                    for (int j=w[i];j<=c;j++)//m(i,j)=max{m(i+1,j-Wi)+Vi,m(i+1,j)}
                        m[i][j]=Math.max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
                }
                m[1][c]=m[2][c];//第一次物品的最优值=第二个物品的最优值
                if (c>=w[1])//获取第一个物品和第二个物品的最优值
                    m[1][c]=Math.max(m[1][c], m[2][c-w[1]]+v[1]);
            }
            static void funB(int m[][],int[] w,int c,int n,int[] x){
                for (int i=1;i<n;i++)
                    if (m[i][c]==m[i+1][c])//如果相邻两个物品的最优值相等，则表示该物品不用放入背包
                        x[i]=0;//不放入表示0
                    else {
       //如果不等，放入背包，然后减去重量
                        x[i]=1;
                        c-=w[i];
                    }
                if (m[n][c]==m[n-1][c])//判断最后一个
                    x[n]=0;
                else
                    x[n]=1;
            }
            public static void main(String[] args) {
                int n=5,c=10;
                int[] w={
       0,6,4,8,8,4};
                int[] v={
       0,8,4,8,10,2};
                int[][] m=new int[n+1][c+1];
                int[] x=new int[n+1];
                int sum=0;
                funA(n, c, m, w, v);
                funB(m, w, c, n, x);
                for (int i=1;i<=n;i++){
                    sum+=x[i]*v[i];
                }
                System.out.println("最优值为"+sum);
            }
        }

(3) 算法运行结果  
计算最优值的时间复杂度O(nc)  
构造最优解的时间复杂度O(n)  
(4) 体会

0-1背包同样都是考虑多种情况。分别为j>=Wi和j<Wi的情况。01背包的状态转换方程 f[i,j] = Max{ f[i+1,j-Wi]+Vi( j >= Wi ), f[i+1,j] }。

[SouthEast]: /images/20220714/a2c485a114cf439986113e6b5a07e043.png
[SouthEast 1]: /images/20220714/70763e77ef7f4cdcb2e7e896945b322c.png