动态规划算法之线路布线问题

/*
 * Filename: wire_layout.c
 *
 * Function: 电路板上有有两排线柱，比如int wire[] = {7,6,3,1,4,0,8,2,9,5};
 *           代表第一排第零个线柱与第二排第7个线柱相连
 *           求在不交叉的情况下，尽可能多地布线
 *
 * Note：
 *
 * Version: 1.0
 * Author:  WUSW
 * Date:    2009.4.27
 */

#include
#include

#define NUM 10

/* to deal the boundary */
int get_size(int size[][NUM], int i, int j)
{
  if (i<0 || j<0)
    {
      return 0;
    }

  return size[i][j];
}

int max(int a, int b)
{
  return a>=b?a:b;
}

void max_wire(const int *wire, int len, int size[][NUM])
{
  int i = 0;
  int j = 0;

  for (i=0; i    {
      for (j=0; j    {
      if (j < wire[i])
        {
          size[i][j] = get_size(size, i-1, j);
        }
      else
        {
          size[i][j] = max(get_size(size, i-1, j), get_size(size,i-1,wire[i]-1)+1);
        }
    }
    }
}

/* to store those selected wire in "wire_set" */
void find_set(int size[][NUM], int *wire, int *wire_set)
{
  int i = 0;
  int j = NUM-1;
  int m = 0;
 
  for (i=j; i>=0; i--)
    {
      if (get_size(size,i,j) != get_size(size,i-1,j))
    {
      j = wire[i] - 1;
      wire_set[m++] = i;
    }
    }
  if (j >= wire[i])
    {
      wire_set[m] = i;
    }
 
}

int main(int argc, char * argv[])
{
  int size[NUM][NUM] = {{0}};
  int wire[] = {7,6,3,1,4,0,8,2,9,5};
  //int wire[] = {2,0,1};
  int wire_set[NUM];        
  memset(wire_set, -1, sizeof(wire_set));

  max_wire(wire, NUM, size);
  find_set(size, wire, wire_set);

  int i = 0;
 
  for (i=0; i    {
      if (wire_set[i] != -1)
    {
      printf("%d ", wire_set[i]);
    }
    }
       
  return 0;
}